[백준] 9012 괄호 (실버4) / 스택

문제요약

나의 코드 및 설명 - for문 사용

• 요소 한 개를 저장한 리스트 ans를 생성하고, for문을 통해 입력한 문자열의 뒤에서부터 거꾸로 확인하여, 닫힌 괄호<)>의 개수보다 열린 괄호<(> 의 개수가 많아지면 ans에 저장된 요소의 개수는 0개가 되고, 그렇다면 NO를 출력하는 코드를 작성하였다.

import sys
n = int(input())

for _ in range(n):
    string = list(sys.stdin.readline().rstrip())
    ans = [0]
    #만약 입력한 문자열에서 '('의 개수와 ')'의 개수가 다르다면 VPS가 아니다.
    if string.count("(") != string.count(")"):
        print("NO")
    #'('의 개수와 ')'의 개수가 같다면,
    else:
        #문자열의 맨 끝부터 확인한다.
        for i in range(len(string)-1, -1, -1):
            #문자가 ')'이라면
            if string[i] == ")":
                #문자열에서 해당 문자를 없애고
                string.pop()
                #ans에 0을 추가한다.
                ans.append(0)
            #문자가 '(' 이라면
            else:
                #ans중 가장 최근에 들어간 0을 제거한다.
                ans.pop()
            #이 때, 만약 ans가 비어있다면, ')'에 비해 '('가 더 많아져서 
            #VPS가 될 가능성이 없다.
            if len(ans) == 0:
                print("NO")
                break
            #만약 ans가 비어있지 않다면 계속해서 반복을 수행한다.
            else:
                continue
        #반복을 수행한 후 ans에 0 하나만 들어있다면 VPS이고, YES를 출력한다.
        if len(ans) == 1:
            print("YES")
        else:
            continue

나의 코드 및 설명 - while문 사용

• 위 코드와 같은 방식의 코드이지만, 이미 제거된 문자열의 뒤에서부터 for문을 통해 살펴본다는 것이 살짝 이상한 것 같아 while문을 사용하여 입력받은 문자열이 빌 때까지 반복문을 수행하며, 열린 괄호의 개수가 더 많아지면 NO를 출력하는 코드를 작성하였다.

import sys
n = int(input())

for _ in range(n):
    string = list(sys.stdin.readline().rstrip())
    ans = [0]
    #만약 입력한 문자열에서 '('의 개수와 ')'의 개수가 다르다면 VPS가 아니다.
    if string.count("(") != string.count(")"):
        print("NO")
    #'('의 개수와 ')'의 개수가 같다면,
    else:
        #문자열 리스트가 빌 때까지 확인한다.
        while string:
            #x에 string 문자열의 마지막 문자를 제거하고 제거된 문자를 x에 저장한다
            x = string.pop()
            #제거된 문자가 ')'이라면
            if x == ")":
                #ans에 0을 추가한다.
                ans.append(0)
            #제거된 문자가 '(' 이라면
            else:
                #ans에 저장된 마지막 값을 하나 제거한다
                ans.pop()
            #이 때, 만약 ans가 비어있다면, ')'에 비해 '('가 더 많아져서 
            #VPS가 될 가능성이 없다.
            if len(ans) == 0:
                print("NO")
                break
            #만약 ans가 비어있지 않다면 계속해서 반복을 수행한다.
            else:
                continue

        #반복을 수행한 후 ans에 0 하나만 들어있다면 VPS이고, YES를 출력한다.
        if len(ans) == 1:
            print("YES")
        else:
            continue

다른 코드 및 설명

• 다른 사람들은 어떻게 문제를 해결했는지 궁금하여 찾아보였다. 
  나랑 풀이 과정은 비슷하나, 이 코드에서는 스택이 아닌 단순 구현으로 문제를 해결한 것을 알 수 있다.
  sum 값을 0 으로 초기화하고, 문자열의 요소들을 for문을 통해 하나씩 확인 후 for문을 마치고 나서 sum 값이 0일 때만 YES를 출력하도록 구현되어있다.

import sys

n = int(input())
for _ in range(n):
    string = list(sys.stdin.readline().rstrip())
    sum = 0
    for i in string:
        if i == "(":
            sum += 1
        elif i == ")":
            sum -= 1
        if sum < 0:
            print("NO")
            break
    if sum > 0:
        print("NO")
    elif sum == 0:
        print("YES")

피드백

처음에는 어떻게 접근해야될 지 헤맸다. 아마 스택을 통해 문제를 해결하면 편하다는 것을 몰랐으면, 단순 리스트로 구현만 해보다가 풀지 못했을 것 같다. 이 문제에서 핵심은 문자열을 뒤에서부터 역순으로 살펴볼 때, 닫힌 괄호의 개수보다 열린 괄호의 개수가 더 많아지면 더 이상 살펴볼 필요 없이 기본 VPS(문제에서 정의한 용어)가 될 가능성이 없다는 것이고, 이것을 이용해서 문제를 해결할 수 있었다.

문자열을 비교 문제가 출제되면 자료구조를 이용해서 문제를 간단하게 풀 수 있다는 것을 항상 생각해야겠다.