4949번 - 균형 잡힌 세상

💡 문제를 똑바로 보는 습관을 들이자!!

import sys

input = sys.stdin.readline

while True:
    
    sentence = list(input().rstrip())
    
    if sentence[0] == '.':
        break
    
    # 괄호를 저장할 stack
    stack = []
    answer = "yes"
    
    for i in sentence:
        
        if i.isalpha() or i.isspace() or i == '.':
            continue
        else:
            if stack and stack[-1] == '(' and i == ')':
                stack.pop()
            elif stack and stack[-1] == '[' and i == ']':
                stack.pop()
            else:
                stack.append(i)
    
    if stack:
        answer = "no"
            
    print(answer)

• 이 문제는 그렇게 어렵지는 않았던 거 같다!! 이 문제의 방법론은 총 3가지가 존재한다.
  => 1. 리스트에 모든 괄호를 모아두고 짝을 하나씩 맞춰보는 방식 => O(n^2)
  => 2. 연결리스트를 이용해서 찾는 방식 => O(n)
  => 3. stack을 활용해서 푸는 방식 => O(n)
  
• 연결리스트로 풀어도 가능하지만, 구현이 쉬운 stack을 활용하여 풀이하였다.
• 기존에 입력값을 통해 sentence로 전부 받아서 저장한후 sentence를 돌면서, 괄호에 해당하는 것만 바로바로 stack에 넣어주면서 짝을 판단하였다.
• 새로운 괄호가 들어올때 마다, stack의 가장 윗부분과 들어온 괄호가 짝이 맞으면, stack의 가장 윗부분을 pop()으로 없애주고, 짝이 맞지 않으면 append()로 stack에 쌓아갔다.
• sentence를 전부 순회한 후, stack의 비어있음 여부로 짝을 잘 찾았는지를 판단하여 답을 도출하였다.

💡 코테스터디에서 나온 기발한 풀이법

import sys
input = sys.stdin.readline

while True:
    string = input().rstrip()  # 입력 문자열을 받고 오른쪽 공백과 개행 문자를 제거
    if string == '.': break  # 문자열이 "."인 경우 반복문을 종료
    for s in string:
        if s not in '()[]':  # 괄호를 제외한 다른 문자들을 모두 제거
            string = string.replace(s, '')
    while '[]' in string or '()' in string:  # 문자열에 괄호 쌍이 있는 동안 반복
        string = string.replace('()', '')  # '()'를 제거
        string = string.replace('[]', '')  # '[]'를 제거
    print('no') if string else print('yes')  # 문자열이 남아있는지 여부에 따라 결과를 출력

• replace함수를 이용하여 처음에 괄호를 제외한 모든 것을 전부 제외시켰고, ()와 []를 세트로 replace시키면서 줄여나가는 방식을 사용하였다.

💡 코테스터디에서 나온 기발한 풀이

    for i in range(N):
        # 문자가 '(' 또는 '['인 경우 스택에 추가
        if inp_list[i] == '(' or inp_list[i] == '[':
            stk.append(inp_list[i])
        # 문자가 ')'인 경우 스택 마지막 인덱스에 '(' 있는지 확인
        elif inp_list[i] == ')':
        # 스택에 '(' 있으면 삭제
            if len(stk) >= 1 and stk[-1] == '(':
                stk.pop()
        # 없으면 쌍이 안맞으므로 no 출력
            else:
                print('no')
                break
        # 문자가 ']'인 경우 스택 마지막 인덱스에 '[' 있는지 확인
        elif inp_list[i] == ']':
        # 스택에 '[' 있으면 삭제
            if len(stk) >= 1 and stk[-1] == '[':
                stk.pop()
        # 없으면 쌍이 안맞으므로 no 출력
            else:
                print('no')
                break
    # 마지막에 스택이 비어있으면 yes 출력
    else:
        print('yes')

• 틀린 풀이긴 한데, 신기했던 것이 for문에도 else가 달린다는 것이였다.
• for문에 else를 달면