[백준/Python] 9012 괄호

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

 

 

사용 알고리즘: 스택

 

 

입력

• 테스트케이스 개수 T
• 밑으로는 T 개의 테스트케이스가 주어지며, 테스트케이스의 괄호 문자열의 길이는 2 이상 50 이하

 

 

괄호의 짝을 맞추는 문제 -> 스택 대표 문제라고 생각하면 됨

 

 

주어진 괄호 문자열을 돌면서 

 

1. '(' 인 경우 스택에 추가

2. ')' 인 경우

• 빈 스택일 경우 짝이 안 맞으므로 answer 에 'NO' 를 기록
• 빈 스택이 아닐 경우 스택의 맨 위의 요소 pop

주어진 괄호 문자열을 다 돌고 나왔는데, 빈 스택이 아닌 경우는 짝이 안 맞는 경우이므로 answer 에 'NO' 를 기록

for _ in range(n):
    s = deque()
    PS = input().rstrip()
    answer = 'YES' # 일단 answer을 YES 로 기록해둠
    for x in PS:
        if x == '(': # ( -> 스택에 추가
            s.append(x)
        elif x == ')':
            if len(s) == 0: # 빈 스택이면 짝 안 맞음 -> answer = 'NO'
                answer = 'NO'
                break
            else: # 빈 스택 아니면 스택 맨 위 요소 pop
                s.pop()
    if len(s) != 0: # 다 돌았는데 빈 스택이 아님 -> 짝 안 맞음 -> answer = 'NO'
        answer = 'NO'
    print(answer)

 

 

 

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    s = deque()
    PS = input().rstrip()
    answer = 'YES' # 일단 answer을 YES 로 기록해둠
    for x in PS:
        if x == '(': # ( -> 스택에 추가
            s.append(x)
        elif x == ')':
            if len(s) == 0: # 빈 스택이면 짝 안 맞음 -> answer = 'NO'
                answer = 'NO'
                break
            else: # 빈 스택 아니면 스택 맨 위 요소 pop
                s.pop()
    if len(s) != 0: # 다 돌았는데 빈 스택이 아님 -> 짝 안 맞음 -> answer = 'NO'
        answer = 'NO'
    print(answer)

 

 

 

시간 복잡도

 

- for 문 내부 연산들

• append: O(1)
• pop: O(1)

- 괄호 문자열을 도는 for문: O(m)

(m: 괄호 문자열의 길이)

 

- 테스트케이스 개수만큼 도는 바깥 for문: O(n)

 

총 시간 복잡도는 O(m*n)