[파이썬] 9012번: 괄호

9012번: 괄호 (acmicpc.net)

9012번: 괄호

 

스택의 원리를 활용하여 푸는 문제이다. 

괄호가 일련으로 입력되면 그 괄호들의 쌍이 서로 맞는지 판단하여 YES, NO를 출력해야 한다. 

 

나의 시도

처음에는 stack이라는 이름의 리스트를 만들어서 거기에 append, pop하는 방식으로 시도했다.

왼쪽 괄호가 나오면 stack에 append 해주고, 오른쪽 괄호가 나오면 stack에 있는 왼쪽 괄호를 팝하여 stack을 비운다. 

반복적으로 이 과정을 수행한 후 stack의 길이가 0보다 크면 NO, 그렇지 않으면 YES를 출력하도록 구성했었다.

 

하지만 이렇게 하면 몇 가지 케이스에서 오류가 발생한다. 

예를 들어, (())()) 에서는 마지막 )에서 팝을 수행해야 하는데 빈 리스트에서 팝을 하기 때문에 IndexError가 뜬다. 

(+22.06.19 추가, 보니까 이런 경우를 언더플로underflow라고 하는 것 같다)

이를 다루기 위해 try, except 구문을 넣어보았지만 최종적으로 괄호쌍의 판단을 stack의 길이로 했기 때문에 오류는 계속해서 발생했다. 

 

 

문제 해결

계속 고민하다 구글링해본 결과 대부분이 sum에 1을 더하고 빼주는 방식으로 해결하고 있었다.

왼쪽 괄호에는 +1, 오른쪽 괄호에는 -1을 하여 최종적으로 sum이 0일 경우에만 YES를 출력한다. 

이 풀이에서는 (())())처럼 오른쪽 괄호만 혼자 남을 때 sum이 음수가 된다. 

마지막 블록에서 sum이 0일 때만 YES, 음수나 양수일 때에는 NO가 출력되므로 이렇게 오른쪽 괄호만 덜렁 남는 경우도 문제없이 다뤄줄 수 있다. 

for _ in range(int(input())):  # 테스트케이스 개수 입력 받기
    sum = 0
    par = input()  # 괄호 입력 받기

    for p in par:
        if p == "(":  # 왼쪽 괄호라면 1 더해주기
            sum += 1
        else:
            sum -= 1  # 오른쪽 괄호가 나오면 sum에서 1 빼주기
        if sum < 0:  # sum이 음수가 되면 반복문 빠져나오기
            break

    if sum == 0:  # sum이 0일 경우에만 YES 출력
        print("YES")
    else:  # sum이 양수이거나 음수인 경우에는 전부 NO
        print("NO")