Seongkyun Han's blog

190225 백준 알고리즘 문제풀기

25 Feb 2019 | baekjoon

[9012] 괄호

문제

  • 괄호가 올바르게 배열 된 것을 VPS라 한다.

  • 주어지는 문자열에서 괄호가 올바르게 열리고 닫히게끔 되면 YES를, 아니면 NO를 출력한다.

  • 첫 문자열이 ‘)’이거나 전제 문자열 길이가 홀수개면 무조건 VPS를 만족하지 못하므로 ‘NO’를 출력한다.
  • 그렇지 않은경우, 문자열에 ‘)’가 포함되어 있다면 ‘)’를 제거하고 바로 ‘(‘를 제거한다.
  • 만약 문자열에 ‘)’가 포함되어 있다면 ‘)’가 남아있는 경우이므로 ‘NO’를 출력한다.
  • 만약 문자열이 모두 제거되어 길이가 0이 된 경우 ‘YES’를 출력한다.

정답

for _ in range(int(input())):
    ps = list(input())
    while len(ps) != 0:
        if ps[0] == ')' or len(ps)%2 != 0:
            print('NO')
            break
        else:
            if ')' in ps:
                ps.remove(')')
                ps.remove('(')
            else:
                print('NO')
                break
    if len(ps) == 0:
        print('YES')
  • 스택을 사용하여 문제를 풀 경우 아래와 같다.
    • 문자열에 ‘(‘가 있는경우 push를 한다.
    • 만약 그렇지 않은 경우(‘)’가 들어오는 경우), 스택이 비어있지 않다면 pop을 한다.
      • 만약 스택이 비어있다면 ‘NO’를 출력한다.
      • 이는 이전에 들어온 ‘(‘가 없는데 현재 ‘)’가 들어왔단 의미이므로 VPS가 절대 될 수 없다.
    • 해당 입력 문자열에 대해 위의 for loop을 돌고 난 후, 만약 스택이 비어있다면 성공적으로 모두 push/pop이 된 것이므로 ‘YES’를 출력한다.

정답

class Stack:
    def __init__(self):
        self.len = 0
        self.list = []

    def push(self, num):
        self.list.append(num)
        self.len += 1

    def pop(self):
        if self.size() == 0:
            return -1
        pop_result = self.list[self.len-1]
        del self.list[self.len-1]
        self.len -= 1
        return pop_result

    def size(self):
        return self.len

    def empty(self):
        return 1 if self.len == 0 else 0

    def top(self):
        return self.list[-1] if self.size() != 0 else -1

stack = Stack()
result = ''
for _ in range(int(input())):
    stack.list = []
    stack.len = 0
    result = ''
    ps = list(input())
    for j in range(len(ps)):
        if ps[j] == '(':
            stack.push(ps[j])
        else:
            if stack.empty() == 0:
                stack.pop()
            else:
                result = 'NO'
                break
    if stack.empty() and result != 'NO':
        print('YES')
    else:
        print('NO')

Related Posts