[Algorithm] 9012. 괄호

유지민·2023년 1월 19일
0

Algorithm

목록 보기
2/67
post-thumbnail

9012. 괄호 (silver IV)

✔️ 문제

9012번 문제 보기

✔️ 문제 분석 및 해결 과정 설계

  • 각각의 테스트 케이스는 독립적

  • 테스트 케이스 하나에 대해 어떻게 해결하면 되는지 알아내면 되는 문제

  • 올바른 괄호쌍을 구하는 문제 : 전형적인 Stack을 사용하는 문제

  • ex) ((()))
    위의 경우 세 쌍의 괄호가 있음
    차례로 여는 괄호를 1, 2, 3이라고 칭한다면, 닫는 괄호는 4, 5, 6
    → 쌍 : (1,6), (2,5), (3,4)
    → 여는 괄호가 들어오는 순서와 닫는 괄호가 들어오는 순서는 역순

  • 현재 스택 상태(Bottom to Top) : 1 2 [3 4] → pop

    • 1, 2, 3 여는 괄호가 들어온 뒤 4번째 닫는 괄호와 함께 POP
  • 현재 스택 상태(Bottom to Top) : 1 [2 5] → pop

    • 1, 2가 있는 스택에 5가 들어올 때 여는 괄호 2와 닫는 괄호 5를 함께 POP
  • 현재 스택 상태(Bottom to Top) : [1 6] → pop

    • 1만이 남아있는 상황에서 닫는 괄호 6이 들어올 때 2와 함께 POP

✔️ 문제 해결 과정

  1. 입력 조건 충족
  2. 한 줄씩 입력받는 문자열을 문자단위로 순회하며 VPS stack.append() or stack.pop() 결정
    → 만약 순회 중인 문자가 (일 경우 : VPS가 되기 위해 )가 들어와야 pop될 수 있으므로 stack.append()
    → 순회 중인 문자가 )일 경우 : VPS의 조건을 만족하므로 )append할 필요 없이 쌍이 되는 (stack.pop()
# step 1
T = int(input())
for _ in range(T):
    stack = [] # list로 Stack 구현
    
    for char in input():
        # 여는 괄호의 경우 stack에 append
        if char == '(':
            stack.append(char)
        # 닫는 괄호의 경우 stack에 있는 여는 괄호와 한 쌍이 이루어지므로 pop
        else:
            stack.pop()

만약 step1에서 입력된 문자열이 ((()))와 같을 경우, 마지막 닫는 괄호가 pop되면 모든 조건을 완료함
((())))()과 같이 6번째 문자(세번째 닫는 괄호)에 stack의 모든 문자가 Pop되고, stack은 비어있는 상태가 됨
→ 이 때 7번째로 들어오는 )의 경우 ? 비어있는 stack에서 stack.pop()명령어가 수행되므로 오류 발생

  1. stack의 원소 개수를 체크하여 stack이 비어있는 경우 vs 차있는 경우를 나누어 처리
# step 2
T = int(input)
for _ in range(T):
    stack = [] # list로 Stack 구현

    for char in input():
        # 여는 괄호의 경우 stack에 append
        if char == '(':
            stack.append(char)
        # 닫는 괄호의 경우
        else:
            # stack - !empty : stack에 있는 여는 괄호와 한 쌍이 이루어지므로 pop
            if len(stack) > 0:
                stack.pop()
            # stack - empty : stack이 비어있으므로 break
            else:
                break

step2까지의 과정을 통해 모든 입력값에 대해 오류 없이 stack 작업을 수행할 수 있게 됨
→ 남은 작업 : 입력된 행이 VPS 조건을 만족할 경우 YES, 만족하지 못할 경우 NO 출력

  1. VPS 조건 체크 플래그 isVPS를 선언해 분기에 따라 플래그 업데이트
# step 3
T = int(input())
for _ in range(T):
    # i가 특별히 할 일이 없을 경우 _로 대체 가능
    stack = [] # list로 스택 구현
    isVPS = True

    for char in input(): # 한줄씩 입력받아 문자 하나씩 순회
        if char == '(':
            stack.append(char)
        else:
            # if stack == if len(stack) > 0
            if len(stack) > 0:
                # ((()))와 같이 여는 괄호와 닫는 괄호가 함께 들어온 경우, 즉 스택이 비게 되는 경우
                stack.pop() # 닫는 괄호가 들어왔기에 여는 괄호를 pop
            else:
                isVPS = False
                break

    if stack:
        isVPS = False

    print('YES' if isVPS else 'NO')

💡 회고

  • python을 오랜만에 하다보니 생각보다 문법적인 부분, 사용해야 하는 자료구조에 대해 빠르게 아이디어가 떠오르지 않았다.
  • 의사코드를 작성함에 있어 ()()()처리는 쉬울 것 같아 보였으나, 오히려 ((()))의 입력값 처리에 대해 막히게 되었다.
    → 후입선출(LIFO)의 특징을 가진 자료구조 stack을 활용해야겠다는 아이디어가 떠오르지 않았으므로 테스트 케이스에 대해 한정적인 사고만이 가능했다.
    ()()()가 쉬울 것 같아 보였던 이유는 배열을 본 문제의 자료구조로 활용하려 하였기 때문. depth가 커지는 것에 대해 인덱스로 접근하는 방법에서 막혔다고 판단된다.
  • 파이썬의 삼항연산자를 처음으로 코드에 적용시켜 보았다. → 유용하다!

✔️ 230825 문제 재풀이

이전에 작성했던 코드를 다시 제출했을 때 오답 처리가 되었다.
그래서 다시 풀이한 코드를 첨부한다!

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    stack = []
    isVPS = True

    for char in input():
        if char == '(':
            stack.append(char)
        if char == ')':
            if stack:
                stack.pop()
            elif not stack:
                isVPS = False
                break
    if not stack and isVPS:
        print('YES')
    elif stack or not isVPS:
        print('NO')
profile
끊임없이 도전하며 사고하는 주니어 Web FE 개발자 유지민입니다.

0개의 댓글