오늘의 회고

오늘은 괄호 회전하기 문제를 풀었다.

---

시도해본 것

처음에는 check함수에서 스택에 열린 괄호들만 넣고 닫힌 괄호를 만났을 때 해당하는 열린 괄호가 있으면 그 괄호를 삭제해주는 방식으로 했었다. 이런 식으로 하면 테스트케이스 14에서 틀리게 된다.

"{(})"

이 경우가 반례이다. 괄호가 열고 닫히는 것만 확인하기 때문에 섞여있어도 맞다고 나오게 된다.

def check(q, idx):
    if idx != 0:
        q.rotate(-1)

    stack = [0]
    for i in range(len(q)):
        if q[i] == '[' or q[i] == '(' or q[i] == '{':
            stack.append(q[i])
        elif (q[i] == ']') and ('[' in stack):
            stack.remove('[')
        elif (q[i] == ')') and ('(' in stack):
            stack.remove('(')
        elif (q[i] == '}') and ('{' in stack):
            stack.remove('{')
        

    if len(stack) == 1:
        return True
    
    return False

---

해결

열린 괄호가 들어있는 스택의 맨 마지막에 있는 괄호가 해당하는 괄호라면 pop해주는 방식으로 하면 된다!!

def check(q, idx):
    if idx != 0:
        q.rotate(-1)

    stack = [0]
    for i in range(len(q)):
        if q[i] == '[' or q[i] == '(' or q[i] == '{':
            stack.append(q[i])
        elif (q[i] == ']') and (stack[-1] == '['):
            stack.pop()
        elif (q[i] == ')') and (stack[-1] == '('):
            stack.pop()
        elif (q[i] == '}') and (stack[-1] == '{'):
            stack.pop()
        else:
            return False

---

정답 코드

from collections import deque

def check(q, idx):
    if idx != 0:
        q.rotate(-1)

    stack = [0]
    for i in range(len(q)):
        if q[i] == '[' or q[i] == '(' or q[i] == '{':
            stack.append(q[i])
        elif (q[i] == ']') and (stack[-1] == '['):
            stack.pop()
        elif (q[i] == ')') and (stack[-1] == '('):
            stack.pop()
        elif (q[i] == '}') and (stack[-1] == '{'):
            stack.pop()
        else:
            return False

    if len(stack) == 1:
        return True
    
    return False


def solution(s):
    answer = 0
    queue = deque()
    for i in s:
        queue.append(i)
    for i in range(len(s)):
        if check(queue, i):
            answer += 1
    return answer