[백준] 2504번 괄호의 값, 괄호 맞추기, 스택 예제, 파이썬

개요

자료구조에서 배운 스택을 활용해서 백준 알고리즘 문제를 풀어보겠습니다.

참고 - [자료구조] 스택(Stack)이란? 스택을 활용해 괄호쌍 확인하기

제가 저번에 포스팅 했던 글입니다. 스택의 개념을 이해하면서 비슷한 예제를 풀었었는데요. 그 예시보다 조금 높은 난이도의 문제입니다.

 

문제

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

2504번: 괄호의 값

 

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어, ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)으로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2 ×값(X)으로 계산된다.
4. ‘[X]’ 의 괄호값은 3 ×값(X)으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어, ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호 값이 2 + 3 × 3=11 이므로 ‘(()[[]])’의 괄호 값은 2 ×11=22이다. 그리고 ‘([])’의 값은 2 × 3=6 이므로 전체 괄호열의 값은 22 + 6 = 28이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

 

입력 : 첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력 : 첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예시 : ( ( ) [ [ ] ] ) ( [ ] )  → 28    # 2 * 2+(3*3) + 2*3    실제 괄호는 없지만 보기 좋으라고 띄워서 적었습니다.

 

풀이

문제를 풀면서 다음 내용을 인지하고 있어야 한다고 생각합니다.

1. 생각보다 많은 경우의 수가 존재한다. 

- 대괄호 안에 소괄호가 들어가야 하는 법칙은 무시하고 해당 수식에 따라 계산을 진행하는 방식입니다. 따라서, 괄호열 안에 2가지 종류의 괄호열이 무수히 들어갈 수 있습니다. 이를 인지하고 있어야 합니다. 

2. 잘못된 괄호열은 3가지로 나누어 생각할 수 있습니다.

- 여는 괄호가 많거나, 닫는 괄호가 많거나, 종류가 맞지 않거나.

3. 연산자 우선순위 

- 괄호에 맞게 바로바로 계산하려고 들면 연산자 우선순위에 맞게 계산할 수 없습니다. 여는 괄호, 닫는 괄호 어느 때 연산을 해도 우선순위에 맞게 계산할 수 없기 때문입니다. 특히, (()()) 와 같은 예시의 경우 (2+2)*2 처럼 안에 있는 괄호열을 먼저 계산해야 합니다. 그래서 끼워 넣으려고 시도하면 답에 멀어질 수 있습니다..

 

위 내용을 인지하고 다음과 같이 문제를 해결했습니다.

 

스택을 생성하여 여는 괄호가 나올 경우 스택에 PUSH하고, 닫는 괄호가 나올 경우 계산 후 다시 스택에 PUSH 합니다. 이 과정을 반복하면 스택의 TOP에는 계산 결과만이 남게 됩니다. 스택의 TOP에 정수가 있을 경우 같은 괄호 안에 있다고 생각하고 덧셈을 했고, 알맞은 닫는 괄호가 나올 때까지 덧셈을 하다가 닫는 괄호가 나오면 그 괄호의 종류에 맞게 곱셈 연산을 진행하여 PUSH 했습니다. 모든 문자열에 대해 반복문을 완료하면 괄호열이 알맞은지 확인하는 절차를 걸친 후 값을 출력했습니다.

 

코드

▲스택 클래스

파이썬의 리스트로도 스택을 구현할 수 있지만, 저번에 만든 스택 클래스를 최대한 활용해서 만들고 싶었습니다.

(저도 모르게 인덱스를 통해서 중간중간 접근하면서 스택을 사용하는 의미를 잃을 수 있기 때문입니다.)

그래서 스택 클래스는 최대한 활용하되, 멤버 함수를 추가했습니다. 추가하지 않고 함수에서 해결할 수도 있었지만, 만, 너무 비효율적이기 때문에 멤버 함수를 추가했습니다. 해서, 보시면 check라는 멤버 함수가 추가된 것을 확인할 수 있습니다. 다음 코드를 보면 알겠지만, 연산이 끝난 후 스택에는 괄호가 남아있으면 안 됩니다. 괄호가 남아있을 경우 올바르지 않은 괄호열로 간주하고 0을 출력한 뒤, 프로그램을 종료합니다.

 

▲prob 함수

해서, 함수를 보시면 반복문 처음에 빈 정수형 변수 temp를 0으로 정의합니다. 스택의 TOP에 정수가 있을 경우 정수를 담는 역할을 합니다. 여는 괄호가 나오면 스택에 PUSH하고, 닫는 괄호가 나오면 알맞은 여는 괄호가 나올 때까지 반복문을 실행합니다. 반복문을 통해 스택의 TOP을 확인합니다. 스택의 TOP에는 괄호가 있을 수도 있고 정수가 있을 수도 있습니다. 먼저 괄호가 나왔을 경우입니다. 바로 여는 괄호가 나왔다면 temp가 0일 것이고 바로 정수(2,3)를 PUSH하면 됩니다. 반대로 정수를 거쳐서 여는 괄호가 나왔다면 temp가 0이 아닐 것입니다. 이 괄호쌍 사이에 있던 정수들은 실제 괄호 안에 들어있던 값이기 때문에 정수를 곱해서 PUSH합니다.

(값을 PUSH할 때 이 전에 있는 괄호를 POP합니다.)

 

다음은 다른 종류의 괄호가 나왔을 경우입니다. 이 경우에는 올바르지 않은 괄호쌍이기 때문에 0을 출력하고 프로그램을 종료 합니다.

 

그리고 정수가 들어 있을 경우, temp에 저장한 뒤 POP합니다.(해당 괄호쌍이 나오기 전까지는 같은 위치에 있는 괄호들이기 때문에 덧셈을 진행합니다.)

▲ 괄호열 검사 및 스택 정리

위 과정을 진행하고 나서 스택의 멤버 함수 check를 통해 스택에 괄호가 남아있는지 확인합니다. 이 과정에서 여전히 괄호가 존재한다면 올바르지 않은 괄호 열입니다. 

 

만약, ( ) ( ) 이 입력되면 스택에는 2, 2라는 값이 쌓이기만 하고 계산은 되지 않습니다.

반복문을 통해서 스택에 있는 값을 계산합니다. 이 경우에는 괄호 안에 존재하는 것이 아니기 때문에 덧셈을 진행합니다.

 

정리

저번에 배운 스택을 활용해서 알고리즘 문제를 풀어봤습니다. 문제를 풀고 나서 다른 사람의 코드를 참고해보니, 제가 너무 고정관념에 갇혀있다는 생각을 했습니다. 조금 더 유연한 마인드로 문제에 임해야겠다는 생각을 했습니다.

 

막상 정답이 나오긴 했지만, 처리 시간과 사용한 메모리를 보면서 조금 아쉬웠습니다. 처리 시간을 줄여보려고 예외처리도 빼보고, 다른 처리들도 많이 해봤지만 차이는 없었습니다. 알고리즘의 문제라고 생각합니다. 계속해서 문제풀이를 하다 보면 더욱 효율적인 코드가 나올 수 있을 것이라고 확신합니다.