Classic_Blue_Note

문제

www.acmicpc.net/problem/2504

풀이

해당 문제는 스택을 이용한 연산을 진행하는 문제이다.

문제 자체를 구현하는데는 시간이 많이 걸리지는 않았으나, 예외 처리 과정에서 디버깅 시간이 많이 걸린 문제였다.

식 자체가 틀린 경우 0을 출력해야 하기 때문에, 리턴을 이용하여 한번에 끝낼 수 있도록 함수를 만들어서 사용하였고, 다양한 조건식을 이용해야 했다.

코드 흐름을 간단히 해설해 보면, 우선 식을 입력받은 뒤, for문을 이용하여 차례대로 탐색을 진행한다.

이 과정에서, try-except 문을 통째로 넣어서, 스택의 크기가 0인데 pop하는 상황이 발생하면 에러가 발생하기 때문에, 해당 에러가 발생할 시 식에 오류가 있다고 판단하고, 바로 0을 리턴할 수 있도록 했다.

이후 정상적인 식일 경우 조건문을 살펴보자.

우선 스택에 아무 값이 없는데 ) 또는 ]가 입력되었을 경우 비정상 식이라고 판단한다.

그리고 비정상 식이 아닌 경우, [나 (가 입력되면 우선 스택에 넣어 둔다.

그리고 이렇게 스택에 쭉 넣어가다가, ]나 )가 입력되는 경우를 확인해 보자.

]나 )가 입력되면, 그 순간부터 스택의 값들을 pop해나가면서 그에 대응되는 반대쪽 괄호가 나올때까지 연산을 진행해 주면 된다.

예를 들어 생각하면, ([]) 라는 식이 있을 때, 해당 식을 (3)으로 만들고, 해당 식을 다시 6으로 만드는 과정인 것이다.

이때 스택에서의 상황을 보면, "(, ["가 들어있다가, ]를 만나면서 [가 pop되고, []이 3으로 변환되어 다시 스택에 들어가면, "(, 3"이 된다.

이러한 형태로 반복 연산을 진행하고, 이때 괄호가 ]를 만나면서 pop을 진행하면 다음 [를 만나기 전까지 스택 내부에는 숫자만 존재해야 하기 때문에 int 형태의 값이 아닌 경우 잘못된 식으로 판단했다.

이런 상황에서 [이후에 바로]을 만나거나, (이후 바로 )를 만나는 경우의 예외처리를 위해 loop_flag라는 값을 이용하여 해당 경우에는 기존 값들을 더하는 것이 아니라, 3또는 2가 바로 스택에 들어갈 수 있도록 처리해 주었다.

이후 마지막에 연산이 모두 끝난 후, 스택의 값들을 확인하여 모두 숫자일 경우 더하고, 숫자가 아닌 값이 하나라도 존재할 경우 식에 오류가 존재한다고 판단하였다.

코드

exp = input()


def cal(expression):
    stack = []
    loop_flag = False
    for i in expression:
        try:
            if len(stack) == 0 and i in "])":
                return 0
                
            if i in "[(":
                stack.append(i)
                
            elif i == "]":
                tmp = stack.pop(-1)
                tmp_num = 0
                while tmp != "[":
                    loop_flag = True
                    if type(tmp) == int:
                        tmp_num += tmp
                    else:
                        return 0
                    tmp = stack.pop(-1)
                if not loop_flag:
                    tmp_num = 1
                loop_flag = False
                tmp_num *= 3
                stack.append(tmp_num)
                
            else:
                tmp = stack.pop(-1)
                tmp_num = 0
                while tmp != "(":
                    loop_flag = True
                    if type(tmp) == int:
                        tmp_num += tmp
                    else:
                        return 0
                    tmp = stack.pop(-1)
                if not loop_flag:
                    tmp_num = 1
                loop_flag = False
                tmp_num *= 2
                stack.append(tmp_num)

        except:
            return 0
            
    val = 0
    
    for i in stack:
        if type(i) == int:
            val += i
        else:
            return 0
    return val


print(cal(exp))

문제

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/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/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))

문제

www.acmicpc.net/problem/10828

풀이

스택을 구현하는 문제이다. 파이썬의 경우, 스택을 직접 구현하지 않고도, 리스트를 이용해서 유연하게 사용할 수 있다.

push의 경우 operand가 존재하기 때문에 입력받을 때부터 split 메소드를 이용하여 입력받았다.

좀더 스택스럽게 구현하기 위해 isempty 함수만 별도로 구현했고, 나머지는 기존 리스트 클래스에 존재하는 메소드를 이용하여 구현하였다.

인덱스 값 중 -1은 맨 뒤의 위치를 의미하는 인덱스이다. append 메소드를 사용하면 리스트에서 자연스럽게 뒤쪽으로 값이 추가되기 때문에, 뒤의 값을 빼내기 위해 -1 인덱스를 활용하였다. insert 메소드를 통해 값을 앞에 넣을수도 있지만, append는 O(1)의 시간 복잡도를 갖고, insert는 O(n)의 시간 복잡도를 갖기 때문에 append 메소드를 활용하였다.

코드

N = int(input())

op_list = []

for i in range(N):
    op_list.append(input().split(" "))


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


st = []

for op in op_list:
    if op[0] == "push":
        st.append(int(op[1]))
        
    elif op[0] == "pop":
        if isempty(st):
            print(-1)
        else:
            print(st.pop(-1))
            
    elif op[0] == "size":
        print(len(st))
        
    elif op[0] == "empty":
        if isempty(st):
            print(1)
        else:
            print(0)
            
    elif op[0] == "top":
        if isempty(st):
            print(-1)
        else:
            print(st[-1])