[Baekjoon] 백준 알고리즘: 9012 - 괄호

문제

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

9012번: 괄호

내가 생각했던 풀이과정

 

기본 VPS인 올바른 괄호 문자열을 만족하려면 

1) 여는 괄호의 갯수와 닫는 괄호의 갯수가 같아야합니다

2) 또한 한쌍의 여는 괄호와 닫는 괄호의 짝이 맞아야합니다

 

이를 스택을 이용하면 쉽게 구현할 수 있습니다. 

 

이 문제의 핵심은 '문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령' 이라고 생각한다는 것입니다

 

 

 

예를 들어, 위의 사진에서 일단 여는 괄호는 리스트에 추가합니다.

 

위의 사진에서 화살표의 위치는 닫는 괄호에 위치해 있습니다. 닫는 괄호는 가장 최근에 들어온 여는 괄호를 없애면 됩니다. 지운 괄호와 닫는 괄호가 모두 노란색이니 짝이 맞아 떨어진 것을 알 수 있습니다.

이제 닫는 괄호는 차례로 지워주면 됩니다. 문자열을 다 읽었고 남아있는 괄호가 없을 때 모든 것이 다 짝이 잘 맞았다는 것을 알 수 있습니다.  이처럼 올바른 괄호 쌍일 경우 여는 괄호를 읽을 때 마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온, 즉 가장 끝에 있는 여는 괄호와 짝을 이루게 해주고 pop을 하면 올바른 괄호 쌍인지 확인할 수 있습니다.

 

올바르지 않은 괄호 쌍의 경우는 3가지가 있습니다.

({)} # 1) 짝이 맞지 않은 경우
({} # 2) 문자열을 다 읽었을 때 여는 괄호가 남아있는경우
()} # 3) 문자열을 다 읽었을 때 닫는 괄호가 남아있는경우

1) 짝이 맞지 않은 경우
2) 문자열을 다 읽었을 때 여는 괄호가 남아 있는 경우
3) 문자열을 다 읽었을 때 닫는 괄호가 남아 있는 경우

 

올바른 괄호 쌍의 판단을 위해 문제 해결 방법은 다음과 같습니다.

 

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나왔을 경우

  2-1) 스택이 비어있으면 올바르지 않은 괄호 쌍

  2-2) 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호쌍

  2-3) 스택의 top이 짝이 맞는 괄호일 경우 pop

3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아 있지 않으면 올바른 괄호 쌍

 

나의 풀이

N = int(input())

for i in range(N):
    isValid = 'YES'
    temp = input()
    bracket = []
    for j in range(len(temp)):
        if temp[j] == '(':
            bracket.append(temp[j])
        else:
            if (len(bracket) == 0 or bracket[-1] != '('):# 스택이 비어있거나 스택의 top이 짝이 맞지 않는 괄호일 경우
                isValid = 'NO'
                break
            elif temp[j] == ')': #스택의 top이 짝이 맞는 괄호일 경우 pop
                bracket.pop()
    if len(bracket) > 0:
        isValid = 'NO'
    print(isValid)

위에서 언급한 문제 해결 방법을 그대로 사용하였습니다.

 

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나왔을 경우

  2-1) 스택이 비어있으면 올바르지 않은 괄호 쌍

  2-2) 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호쌍

  2-3) 스택의 top이 짝이 맞는 괄호일 경우 pop

 

스택의 top을 확인하기 위해 배열[-1]을 사용하였습니다.

 

3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아 있지 않으면 올바른 괄호 쌍

다른 사람의 풀이

a = int(input())
for i in range(a):
    b = input()
    s = list(b)
    sum = 0
    for i in s:
        if i == '(':
            sum += 1
        elif i == ')':
            sum -= 1
        if sum < 0:
            print('NO')
            break
    if sum > 0:
        print('NO')
    elif sum == 0:
        print('YES')

여는괄호가 나오면 sum에 1을 더해주고, 닫는괄호가 나오면 1을 빼준다.

여기서 -1이 되면 NO를 출력해주고 for문을 빠져나오고 있습니다. 음수가 된다는 의미는 여는 괄호없이 닫는 괄호만 있다는 뜻입니다.

sum이 0보다 크다면 NO를 출력해주는데 문자열을 다 읽었는데도 sum이 0이상이면 여는괄호가 남아있다는 뜻입니다.

sum이 0이라면 짝이 맞다는 이야기이기 때문에 YES를 출력해준다.

 

새로 알게된 점, 확인해야할 점

스택의 top: 배열[-1] 형태로 확인할 수 있습니다.

 

• 참고

- 바킹독 님의 ' 알고리즘 풀이 ' : https://blog.encrypted.gg/936?category=773649