[백준] 2504번:괄호의 값

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

2504번: 괄호의 값

자료구조 전공책에서 흔히 나오는 괄호쌍을 따지는 문제였기에 단박에 스택을 쓰면 풀 수 있겠다는 생각이 드는 문제이다.

대신 스택의 메모리 문제 때문에 꽤 시간이 걸렸다.

우선 되는 테스트케이스, 안되는 테스트 케이스를 추가하여 스택 풀이법을 구체화했다.

쉽게 풀기 위해서는 우선 되는 테스트케이스부터 시도해보고, 안되는 테스트케이스를 적용해 코드를 작성했다.

문제의 예시에 맞춰 조금씩 스택으로 풀어서 설명해보겠다.

()[[]]

문자	스택	세부 내용
(	(	push (
)	2	소괄호 완성했으므로  pop ( push 2
[	2[	push [
[	2[[	push [
]	2[3	대괄호 완성했으므로 pop ] push 3
]	29	[를 만날 때까지 숫자를 pop한다. 숫자들을 모두 더한 뒤, 3을 곱해준다.

이렇게 문자열을 순회한 뒤, 스택에 남은 숫자들만 더해주면 완성이다.

🚫 주의

스택을 이렇게 쓸 계획에 괄호 문자와 수를 모두 저장할 수 있도록 처음에는 stack<char>을 쓰려고 했다.

하지만 char 타입의 경우 1바이트, 즉 범위가 -8~8까지만 커버 가능한 자료형이다.

그래서 9 이상의 수를 저장하려고 하자 바로 고장나버렸다..

 

이러한 문제를 해결하기 위해서 연산 결과가 커질 것을 대비하여 stack<long long>으로 지정해두었다. 그리고 괄호의 경우에는 음수로 처리하여서 구분할 수 있었다. 문제에 의하면 스택에 숫자가 push 되는 경우는 오직 2 이상의 양수들만 등장하기 때문에 그렇게 처리할 수 있었다.

 

또한 스택에 접근할 때 반드시 스택이 empty한 지 확인해야했다. 만약 empty한 스택의 top에 접근하거나, pop을 할 경우 백준에서는 Segmentation Fault 즉 메모리 참조 문제가 발생한다...(운영체제 시간에 맛본 지옥의 Segmentation Fault....😵‍💫)

 

경우의 수 

예외 처리

- 만약 문자열의 길이가 홀수이면 절대로 올바른 괄호열이 아니다.

 

1) [

스택에 push

 

2) (

스택에 push

 

3) ]

- 스택이 empty한지 확인하고 empty하면 0 출력

- 스택의 top이 [이면 [ pop하고, 3 push

- 아니라면 [ pop될 때까지 스택의 값들을 더한다. 만약 숫자나 [이 아닌 값이 나오면 0 출력

- 스택이 비지 않은 경우를 전제하고, 즉 올바른 괄호식이라는 가정 하에만 [을 pop하여 위에서 더한 값 * 3을 push

 

 

4) )

- 스택이 empty한지 확인하고 empty하면 0 출력

- 스택의 top이 (이면 ( pop하고, 2 push

- 아니라면 ( pop될 때까지 스택의 값들을 더한다. 만약 숫자나 (이 아닌 값이 나오면 0 출력

- 스택이 비지 않은 경우를 전제하고, 즉 올바른 괄호식이라는 가정 하에만 (을 pop하여 위에서 더한 값 * 2을 push