코드

# 내가 작성한 코드
while True:
    # 찾아야할 괄호
    bracket = '()[]'
    
    str_ = input()
    
    if str_ == '.':
        break
        
    # 괄호를 받아줄 스택 => 이 스택에 있는 요소를 비교하여 균형 여부 확인
    stack = []
    
    # 입력받은 문자열을 하나씩 비교
    for i in str_:
        
        # i가 괄호 리스트안에 없으면 아무런 작업할 필요없음 
        if i not in bracket:
            # print('괄호 아님')
            continue
            
        # i가 여는 괄호라면 스택에 추가
        if i == '(' or i == '[':
            stack.append(i)
            
        # i가 닫는 괄호이고, 스택이 비어있지 않으며 스택의 맨 마지막이 열린 괄호인 경우
        # and stack을 하지 않으면 스택이 비어있는 경우에도 stack[-1]가 작동하여
        # indexError가 발생
        # 한쌍의 괄호가 만들어짐 => pop()으로 스택에서 제거함 
        elif (i == ')' and stack and stack[-1] == '(') or (i == ']' and stack and stack[-1] == '['):
            stack.pop()
            
        # 위의 경우가 아닌 경우, 그냥 스택에 아무거나 넣어준다
        # 스택이 비어있는 경우에만 yes이므로 뭐라도 넣어줘야 함
        # 이때, 어차피 문제의 요구 조건에서 벗어났으므로 반복을 중지시킨다
        else:
            stack.append('Junk Data')
            break

    # st가 비어있지 않으면 no 비어있으면 yes 출력
    print('no' if stack else 'yes')

문제 해설

개인적으로 제법 어렵게 느껴진 문제이다. 처음 문제 접근을 완전히 다른 방식으로 해서 그 방식에서 벗어나느라 많이 애를 먹었다.

참고 블로그

괄호 쌍을 찾아서 저장하는 형식으로 푸는 문제이므로 스택을 활용하여 풀면 된다. (파이썬은 기본 리스트가 스택의 기능을 모두 갖추고 있어 리스트로 진행)

입력받은 문자열 중 괄호가 아닌 경우는 continue로 반복을 넘기고 여는 괄호인 경우에만 스택에 저장을 해준다. 닫는 괄호가 들어오는 경우, 이미 스택에 여는 괄호가 있는 경우에만 괄호 쌍으로 인정되므로 고려해야하는 조건이 아래와 같이 있다.

  • 스택이 비어있다면 올바는 괄호 쌍이 아니다. => 스택엔 여는 괄호만 들어갈 수 있는데 비어있다는 것은 여는 괄호보다 닫는 괄호가 먼저 들어왔다는 뜻이므로 문제에서 요구하는 문자열이 될 수 없다.

달리 얘기하자면

  • 닫는 괄호가 들어올 때, 스택의 맨 마지막이 여는 괄호인 경우에만 괄호 쌍으로 인정이 된다.

위 조건이 성립하면 한 쌍이 완성됐으므로 해당 괄호는 더 이상 고려해선 안 되기 때문에 스택에서 여는 괄호를 pop() 메소드로 제거한다.

마지막으로 아무런 조건에도 부합하지 않을 경우, 스택에 아무 값이나 넣어줌으로써 올바르게 괄호가 짝지어졌을 경우에만 스택이 비어있을 수 있도록 구현한다.

댓글남기기

참고