Baekjoon 9012 괄호

문제 이해

문자열을 읽으면서 “()”가 나오면 문자열에서 없애버리는 방식으로 하나하나 없앤 다음 더 이상 “()”가 나올 수 없을 때 괄호가 남아있다면 NO, 문자열이 완전히 비워졌다면 YES를 출력하면 될 것 같다.

스택으로 치면 문자열을 하나씩 스택에 담다가 “()”가 나오면 그것만 빼서 없애버리기 정도로 볼 수 있을 것 같다.

입출력 조건 확인

그냥 while문으로 문자열 한번 돌릴 것이기 때문에 시간 복잡도는 O(N), 공간 복잡도는 주어진 문자열 리스트에서 크게 벗어나지 않아서 고려하지 않아도 될 것으로 보인다.

문제 풀이 내용 정리

앞에서부터 문자열을 읽으면서 “()”가 나오면 문자열에서 “()”를 제거하고 이전 인덱스로 돌아갔다.
이전 인덱스로 돌아간 이유는 문자열 제거로 인해 새로운 “()”가 생겼을 수 있으므로…

그리고 while문은 point와 매개변수 N의 길이가 같아져버리면 종료되게 만들었다.
0인 상태로 같아지면 YES이고 뭔가 남아서 0 이상이 되었다면 NO를 출력했다.

Python

def VPS(N):
    point = 0
    while(True):
        if len(N) == point:
            if len(N) == 0:
                return print("YES")
            else:
                return print("NO")
        if N[point:point + 2] == "()":
            N = N[:point] + N[point + 2:]
            point -= 1
        else:
            point += 1

T = int(input())
N = []
for i in range(T):
    VPS(input())

코드 문제점 및 해결 방법

SWEA의 기억을 되짚으며 입력을 받아봤는데 이게 맞는지는 모르겠다.

스택으로 코딩해도 되지만 굳이 저장공간을 더 먹기 싫어서 유사하게 리스트 위에서 굴려봤는데 그다지 아름다운 코드는 아닌 것 같다. 더 좋은 방법이 있을 것 같은데…