9012: 괄호 - Python

문제

https://www.acmicpc.net/problem/9012

풀이 1-1 (deque 사용)

from collections import deque

for _ in range(int(input())):
    s = input()
    stack = deque()
    for c in s:
        if c == "(":
            stack.append(c)
        elif c == ")":
            if stack:
                stack.pop()
            else:
                stack.append(c)
                break
 
    if not stack:
        print("YES")
    else:
        print("NO")

• 전통의 스택 문제다. 4949: 균형 잡힌 식단보다 쉽다.

풀이 1-2 (list 사용)

for _ in range(int(input())):
    s = input()
    stack = []
    for c in s:
        if c == "(":
            stack.append(c)
        elif c == ")":
            if stack:
                stack.pop()
            else:
                stack.append(c)
                break
 
    if not stack:
        print("YES")
    else:
        print("NO")

• 알고리즘은 풀이 1-1과 동일하며, stack에 deque 대신 list를 사용했다.
• 막연히 deque이 더 성능이 좋을 것 같아서 사용했는데, 제출 결과 list가 시간, 메모리 측면에서 더 우수했다.
• 조사해보니 단순 stack 용도로는 list가 deque보다 우수하거나 최소 동일한 성능을 보인다고 한다. 이에 대해서는 오늘의 교훈에 적어두겠다.

풀이 2

for _ in range(int(input())):
    s = input()
    cnt = 0

    for c in s:
        if c == "(":
            cnt += 1
        else:
            cnt -= 1

        if cnt < 0:
            break
    
    if cnt == 0:
        print("YES")
    else:
        print("NO")

• stack 변수에 괄호 문자를 저장하는 대신 cnt 변수로 (: +1, ): -1로 카운팅했다.
• 정수 변수를 사용하는 아이디어는 GPT가 제시해줬다.

---

오늘의 교훈

• 단순 stack 용도로는 list가 deque보다 우수하거나 최소 동일한 성능을 보인다.
  • list는 오른쪽 끝에서 삽입/삭제의 평균 시간복잡도가 O(1)이다.
  • deque은 양쪽 끝에서 삽입/삭제의 평균 시간복잡도가 O(1)이다.
  • 다만, stack처럼 항상 오른쪽 끝에서만 push, pop 하는 간단한 경우라면 list가 구현 간결성 및 실제 실행 속도 측면에서 유리한 경우가 많다.
• deque는 양쪽에서 삽입/삭제가 빈번하게 일어날 때 유리하다.
  • 예시) 큐(Queue) -> 왼쪽 끝에서 pop이 필요함
• list는 한쪽 끝에서만 사용하면(append, pop) 내부적으로 메모리를 한 번에 재할당할 필요가 없어 상당히 효율적이다.

• 괄호가 한 종류일 때는 stack 대신 정수형 변수만으로 구현이 가능하다.