[BOJ] 2504 : 괄호의 값 [자료구조](Python)

문제 링크

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

2504번: 괄호의 값

소스 코드

string = input()
stack = []
score = 0
ratio = 1 # 이 비율에 따라 점수를 계산

for idx in range(len(string)):
    if string[idx] == '(': # 여는 괄호인 경우
        ratio *= 2     
        stack.append(string[idx])
    elif string[idx] == '[': # 여는 괄호인 경우
        ratio *= 3
        stack.append(string[idx])
    elif string[idx] == ')': # 닫는 괄호인 경우
        if not stack: # 스택이 비어 있으면 에러
            print(0)
            exit(0)
        # 다른 종류의 괄호를 만나도 에러
        elif stack and stack[-1] == '[':
            print(0)
            exit(0)
        else: # 올바른 괄호쌍인 경우
            stack.pop()
            # 직전 괄호가 닫는 것이면 점수를 추가하지 않음
            if string[idx-1] == ']' or string[idx-1] == ')':
                ratio //= 2
            else: # 직전 괄호가 여는 것이라면 점수를 추가
                score += ratio                    
                ratio //= 2
    else: # 닫는 괄호인 경우
        if not stack: # 스택이 비어 있으면 에러
            print(0)
            exit(0)
        # 다른 종류의 괄호를 만나도 에러
        elif stack and stack[-1] == '(':
            print(0)
            exit(0)
        else: # 올바른 괄호쌍인 경우
            stack.pop()
            # 직전 괄호가 닫는 것이면 점수를 추가하지 않음
            if string[idx-1] == ']' or string[idx-1] == ')':
                ratio //= 3
            else: # 직전 괄호가 여는 것이라면 점수를 추가
                score += ratio                    
                ratio //= 3
if stack: # 스택이 비어있지 않으면 올바른 괄호쌍이 아님
    print(0)
else: print(score)

 

해설

• 스택 자료구조 문제
• 단순 구현 문제

올바른 괄호쌍

이전에 유사한 괄호 관련 스택 문제를 풀어봤다면 올바른 괄호쌍을 어떻게 판별하는지 쉽게 알 수 있습니다.

비어있는 스택을 하나 만들고, 리스트 내 원소를 순서대로 확인하면서 여는 괄호는 스택에 그대로 추가, 닫힌 괄호는 스택의 마지막 원소와 짝을 이룰 경우에만 통과시키면 됩니다.

짝을 이루는 괄호가 나타나는 경우엔 stack.pop( )을 수행해서 짝을 이룬 여는 괄호를 제거해줍니다.

 

모든 원소에 대해 위 작업이 끝났을 때, 스택이 비어있지 않다면 짝을 이루지 못한 괄호가 존재한다는 뜻이므로 올바르지 않은 괄호 문자열이 주어졌다는 것을 알 수 있습니다.

 

간단한 관련 문제 링크입니다.

위 스택 개념이 잘 이해되지 않는다면 먼저 풀어보시기를 권장합니다.

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

9012번: 괄호

괄호 안의 괄호 -> 분배 법칙

이 문제가 까다로운 이유는 괄호 안의 괄호를 계산하는 로직을 짜기가 어렵기 때문입니다.

예전에 풀어봤을 때는 결국 혼자 풀지 못하고 다른 분의 풀이를 참고했었는데, 이번에는 한 시간 정도 고민한 끝에 구현할 수 있었네요.

 

우선 열린 괄호를 만났을 때 스택에 추가하는 것은 동일합니다.

이때 각 괄호(소괄호, 대괄호)에 맞게끔 비율을 늘려줍니다.

이렇게 하는 이유는 우리가 각 괄호에 분배 법칙을 적용할 것이기 때문입니다.

 

닫힌 괄호를 만났을 때는 조금 세 가지 케이스로 구분합니다.

1) 스택이 비어 있는 경우

이런 경우는 열린 괄호 없이 닫힌 괄호가 나타난 것이므로 0을 출력하고 프로그램을 종료합니다.

 

2) 스택이 비어 있지는 않지만 스택의 마지막 괄호가 쌍을 이루지 못하는 경우

이때는 괄호쌍이 제대로 생성되지 않으므로, 마찬가지로 0을 출력하고 프로그램을 종료합니다.

 

3) 괄호쌍이 제대로 생성되는 경우

괄호쌍이 제대로 생성되기 때문에 스택의 마지막 원소를 제거해줍니다.

단, 지금 확인하는 괄호의 직전 괄호가 닫힌 괄호였는지 아닌지를 확인해야 합니다.

만약 지금 닫는 괄호의 직전 괄호도 닫는 괄호라면 스코어를 계산하면 안 됩니다.

구체적인 예를 통해 이해를 돕겠습니다.

 

문제에서 나타난 예시의 일부는 ( ( ) [ [ ] ] ) 입니다.

처음 stack = [ ], ratio = 1, score = 0 입니다.

1) 열린 괄호를 만나 stack = [ '(' ], ratio = 1*2, score = 0입니다.

2) 열린 괄호를 만나 stack = [ '(', '(' ], ratio = 2*2, score = 0입니다.

3) 닫힌 괄호가 짝을 이루어 stack = [ '(' ], ratio = 4//2, score = 0+4입니다.

4) 열린 괄호를 만나 stack = [ '(', '[' ], ratio = 2*3, score = 4입니다.

5) 열린 괄호를 만나 stack = [ '(', '[' , '[' ], ratio = 6*3, score = 4입니다.

6) 닫힌 괄호가 짝을 이루어 stack = [ '(', '[' ], ratio = 18//3, score = 4+18입니다.

7) 닫힌 괄호가 짝을 이루어 stack = [ '(',], ratio = 6//3, score = 22입니다.

8) 닫힌 괄호가 짝을 이루어 stack = [ ], ratio = 2//2 = 1, score = 22입니다.

 

단순히 닫힌 괄호를 만났을 때 점수를 추가하게 되면 7번, 8번 단계에서도 괄호가 닫히면서 ratio만큼 score값이 오르게 됩니다.

따라서 닫힌 괄호를 만났더라도 '직전의 괄호가 닫힌 것인지 아닌지'에 따라서 점수를 추가할 지 말 지 정해주는 조건을 추가해줘야 합니다.

 

간단히 요약하면 괄호가 열리는 것은 그 안의 값들을 전부 곱해준다는 의미가 되므로 ratio값을 키워주고, 괄호가 닫힐 때는 지금까지 계산된 ratio값을 단 한 번만 score에 더한 뒤 짝을 이룬 괄호를 제거해줘야 한다는 것입니다.