[프로그래머스 lv 2] 올바른 괄호 (스택/큐)

아이디어 : 어...? 이 문제는 학교 전공 시험 문제에 나왔던 것과 매우 유사하다. 큐 돌리면서 (이냐 )이냐에 따라 if문으로 큐에 넣고 빼면 될 것 같다.

 

# 첫 번째 시도

from collections import deque

def solution(s):
    answer = True
    queue = deque()
    
    for i in range(len(s)):
        if not queue:
            queue.append(s[i])
        elif queue[0]!=s[i]:
            queue.popleft()
            queue.append(s[i])
    if queue[0]=='(':
        answer=False
    return answer

 

왜 틀렸을까? 생각해보니 ')))' 이렇게 나오는 경우를 빼먹은 것 같다. 그리고 ')'로 시작하는 경우도 예외를 둬야 한다. 그 외에도 조건문 설정을 조금 잘못한 것 같다 -> 단순히 부호가 바뀌는 것 뿐 아니라 "("와 ")"이 짝이 되어야 한다는 조건이 필요하다.

 

# 두 번째 시도

 

(와 )의 갯수도 같아야 하는 거였나? " ())((()))(() -> False"라는 반례를 추가해보았다.

 

from collections import deque

def solution(s):
    answer = True
    queue = deque()
    
    if s[0]==')':
        return False
    flag = False
    
    for i in range(len(s)):
        if not queue: #비어있을 때
            queue.append(s[i])
            if s[i]==')':
                flag = True
                break
        else:
            if queue[0]==s[i]:
                queue.append(s[i])
            else:
                queue.popleft()

    if flag or queue:
        answer = False

    return answer