Classic_Blue_Note

문제

www.acmicpc.net/problem/10799

풀이

스택을 사용하는 문제이다. 스택 개념을 이용하되, 예외 처리를 충분히 해 줘야 한다.

처음에는 해당 문제를 풀 때 플래그를 사용하지 않고, )를 만나면 바로 스택의 길이만큼 더해 주었다. 하지만 그렇게 진행했을 경우, )를 2회 연속으로 만났을 때 문제가 발생했다. ) 이후에 )가 오는 상황은 레이저가 존재하는 상황이 아니고, 항상 막대가 끝나는 부분이기 때문에 이때 막대 전체를 자르는 것이 아니라, 막대가 끝난다는 의미로 코드를 진행시켜야 한다. 따라서, (다음에 )가 오는 경우는 레이저로 자르는 경우이기 때문에 그 때 존재하는 막대의 개수인 스택의 크기만큼 조각 개수를 추가해 주고, )다음에 )가 오는 경우는 막대가 끝나는 경우이기 때문에 마지막 조각이라는 의미로 1만큼 조각 개수를 추가해 주었다. 해당 부분은 플래그 변수를 이용해서 구성했다.

코드

exp = input()


stack = []
piece = 0
flag = False

for i in exp:
    if i == "(":
        stack.append(i)
        flag = False
    else:
        if flag:
            stack.pop(-1)
            piece += 1
        else:
            stack.pop(-1)
            piece += len(stack)
            flag = True

print(piece)

문제

www.acmicpc.net/problem/1935

풀이

후위 표기식을 스택을 이용하여 연산하는 문제이다.

우선 알파벳을 인식하기 위해, 파이썬의 in 연산을 사용하였으며, 인덱스 값을 통해 알파벳에 해당하는 숫자를 확인하였다.

이후 스택에 값을 넣어 가면서 연산자가 나오면 스택의 값을 빼내서 연산하는 과정을 반복하였다.

출력 시 소수 아래 2번째 자리까지 출력하기 위해 % 서식을 이용하여 문자열 포매팅을 진행하였다.

코드

N = int(input())

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

stack = []
exp = input()
data = []

for i in range(N):
    data.append(int(input()))

for i in exp:
    if i in alphabet:
        stack.append(data[alphabet.index(i)])
    else:
        stack.append(float(eval(str(stack.pop(-2)) + i + str(stack.pop(-1)))))
print("%0.2f" % stack[0])

문제

www.acmicpc.net/problem/1874

풀이

스택을 이용하여 수열을 완성해야 하는 문제이다. 기본적인 스택 사용법을 아는지에 대해 묻는 문제로, 약간의 생각을 필요로 하는 문제였다.

해당 문제에서의 핵심은 문제의 이해이다. 필자도 처음에는 문제 자체를 이해하는데 약간의 시간이 걸렸는데, 이후 스택을 어떤 식으로 사용하라는 말인지 이해한 후에는 쉽게 문제를 풀 수 있었다.

필자는 isstackable이라는 함수를 이용하여 문제를 풀이하였는데, 그 이유는 결과값이 불가능한 경우, NO를, 가능한 경우 어떤 연산을 진행했는지 순서대로 출력해야 하기 때문에, 함수 내부에서 리턴 값을 이용하여 불가능한 경우에는 "NO"라는 원소 하나를 가진 리스트로, 가능한 경우에는 연산 리스트를 리턴하도록 했다. 그리고 해당 값을 이터레이터를 이용하여 순차적으로 출력하는 과정을 통해 출력을 용이하게 할 수 있도록 풀이하였다.

함수의 내부 동작 원리는 우선 기본 숫자 배열을 만든다. 이후 두 개의 인덱스를 이용하여 하나는 기본 숫자 배열을 가리키고, 하나는 입력값 숫자 배열을 가리키도록 이용하여 스택의 가장 위 값과 입력값 숫자 배열의 인덱스 위치의 원소가 일치하지 않을 경우 기본 숫자 배열의 값을 스택에 넣고 다음 인덱스로 넘어가는 식으로 구성하였으며, 스택이 비어 있는 경우에는 무조건 스택에 원소를 넣도록 구현하였다.

이후 과도한 오버헤드를 방지하기 위해 기본 숫자 배열의 마지막 원소까지 1차적으로 확인이 끝났으면 이제 남은 원소는 모두 스택 안에 존재하는 것이기 때문에 스택의 모든 값을 빼내고, 새롭게 만들어진 배열과 처음에 입력받은 배열이 서로 같은지 확인을 통해 스택을 통해 해당 배열을 만드는 것이 가능한지 확인하고, 결과값에 따라 리턴하였다.

해당 문제는 디버그 과정에서 약간 시간을 썼는데, 처음에는 마지막 스택을 완전히 마무리하는 과정에서 연산자 리스트에 pop했다는 내용을 넣어주지 않아서 틀린 결과가 나왔었다. 결국 디버깅이 알고리즘 연습의 시간을 좌우한다는 생각이 들었으며, 하나하나 차근차근히 디버깅하는 습관을 가지면 어떤 문제든 해결할 수 있을 것이라고 믿는다.

코드

import sys

N = int(input())

final_data = [int(sys.stdin.readline()) for i in range(N)]


def isstackable(final_data):
    data = [i for i in range(1, N + 1)]
    op_list = []
    stack = []
    my_data = []
    idx = 0
    idx2 = 0
    while idx2 < len(data):
        if len(stack) == 0:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
            continue
        if stack[-1] != final_data[idx]:
            stack.append(data[idx2])
            idx2 += 1
            op_list.append("+")
        else:
            idx += 1
            my_data.append(stack.pop(-1))
            op_list.append("-")
    for i in stack[::-1]:
        my_data.append(i)
        op_list.append("-")
    if my_data == final_data:
        return op_list
    else:
        return ["NO"]


ans = isstackable(final_data)
for i in ans:
    print(i)

문제

www.acmicpc.net/problem/2164

풀이

큐 자료구조를 사용하는 문제이다. 선입선출의 원리를 이용한다.

자료구조는 python collections 모듈의 deque를 사용했고, 해당 자료구조를 이용하여 큐를 구현하였다.

큐 자료구조의 원리를 안다면 간단히 풀리는 문제이다.

종종 인덱스 에러가 발생하는 경우가 있는데, 인덱스 에러가 발생할 경우 경계값 부분을 디버깅 해 볼 필요가 있다. 조건을 확인하고, 해당 조건에서는 1과 500000이 경계값이므로 해당 값이 적절하게 들어가는지 확인해 볼 필요가 있다.

코드

from collections import deque

N = int(input())

queue = deque()

for i in range(N):
    queue.appendleft(i+1)

while True:
    if len(queue) == 1:
        break
    queue.pop()
    tmp = queue.pop()
    queue.appendleft(tmp)

print(queue[0])

문제

www.acmicpc.net/problem/18258

풀이

이번 문제는 큐를 구현하는 문제이다. 파이썬에서는 collections 모듈의 deque 클래스를 이용하여 큐를 이용할 수 있다.(엄밀히는 덱이지만, 덱을 큐처럼 사용하면 된다.)

앞의 스택 구현 문제와 유사하게, isempty 함수만 별도로 구현하여 사용하였고, 나머지는 바로 출력하였다.

그러나 처음에는 시간 초과 에러가 발생했는데, 이유를 처음에는 찾지 못했으나 최대한 시간을 줄이기 위해 구글링해 본 결과 입력 과정에서 오버헤드가 발생한다는 것을 확인할 수 있었다. 실제로 sys.stdin.readline() 메소드를 이용하여 입력받으니 시간 초과가 발생하지 않았으며, 문제를 정상적으로 해결할 수 있었다.

이번 문제를 풀면서 큐의 기본적인 사용 방법을 확인할 수 있었고, 파이썬의 입력 과정에서 생각보다 큰 오버헤드가 발생할 수 있다는 점을 알 수 있었다. 다음부터는 sys 모듈을 이용하여 입력받는 습관을 들이는 편이 시간 단축에 더 유리할 것 같다.

코드

from collections import deque
import sys

N = int(input())


def isempty(data):
    return len(data) == 0


queue = deque()

for i in range(N):
    cmd = sys.stdin.readline().split()
    if cmd[0] == "push":
        queue.append(int(cmd[1]))
        
    elif cmd[0] == "pop":
        if isempty(queue):
            print(-1)
        else:
            print(queue.popleft())
            
    elif cmd[0] == "size":
        print(len(queue))
        
    elif cmd[0] == "empty":
        if isempty(queue):
            print(1)
        else:
            print(0)
            
    elif cmd[0] == "front":
        if isempty(queue):
            print(-1)
        else:
            print(queue[0])
            
    elif cmd[0] == "back":
        if isempty(queue):
            print(-1)
        else:
            print(queue[-1])

문제

www.acmicpc.net/problem/9012

풀이

스택 개념을 이용하되, 실제로 스택을 구현하지 않고 풀이하였다.

우선 데이터를 입력받은 뒤, VPS를 확인해주는 함수를 작성하였다. 이때, VPS를 판별하기 위해 별도의 sum이라는 값을 활용했는데, 예외 상황을 모두 고려하기 위해 if-else문을 이용하여 작성하였다.

(을 만날 때마다 1씩 더하고, )을 만나면 1을 뺀다. 이때 (가 모두 사라진 상태에서 )를 만날 경우 VPS가 아니기 때문에 NO를 출력한다.

모든 연산이 끝난 상태에서 (와 )의 개수가 같을 경우 sum값이 0이어야 하기 때문에, 이때 YES를, 아닌 경우 NO를 출력한다.

연산이나 저장 장소가 필요한 경우 스택을 사용해도 되지만, 이 문제에서는 별도의 연산이 필요 없고, 존재 유무 및 스택의 길이 정도만 확인하면 되기 때문에 스택을 직접 사용하지는 않고 해당 개념만 차용했다.

코드

T = int(input())

data = []
for i in range(T):
    data.append(input())


def VPS(test):
    sum = 0
    
    for char in test:
        if char == "(":
            sum += 1
            
        else:
            if sum == 0:
                return "NO"
                
            else:
                sum -= 1
                
    if sum == 0:
        return "YES"
        
    else:
        return "NO"

for test in data:
    print(VPS(test))