[백준 2504] 괄호의 값 - C++ / 알고리즘 '스택'

문제

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

2504번: 괄호의 값

나의 코드 - 런타임 에러....

(솔직히 처음부터 이러한 아이디어가 떠오르지 않았다...

머리가 안 돌아가서 컴퓨터 뒤적이다가 괄호만이 아니라 계산된 결과값을 스택에 넣을 수 있다는 발상을 볼 수 있었다!

- 처음부터 이런 아이디어가 떠올랐으면 ㅠ..ㅠ)

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int check(string str) {
	stack <char> s;
	int len = str.length();
	int temp = 0;
	long long ans = 0;

	for (int i = 0; i < len; i++) {
		if (str[i] == '(' || str[i] == '[') {
			s.push(str[i]);
		}
		else if (str[i] == ')') {
			if (s.empty() || s.top() == '[' || s.top() == ')' || s.top() == ']')
				return 0;
			else {
				if (s.top() == '(') {
					s.pop();
					temp = 2;
				}
				else { //s.top()가 숫자인 경우
					while (s.top() != '(') {
						temp += s.top() - '0';
						s.pop();
					}
					temp *= 2;
					s.pop();
				}
			}
		}
		else if (str[i] == ']') {
			if (s.empty() || s.top() == '(' || s.top() == ')' || s.top() == ']')
				return 0;
			else {
				if (s.top() == '[') {
					s.pop();
					temp = 3;
				}
				else { //s.top()가 숫자인 경우
					while (s.top() != '[') {
						temp += s.top() - '0';
						s.pop();
					}
					temp *= 3;
					s.pop();
				}
			}
		}
		
		if (temp != 0) {
			s.push(temp + '0');
			temp = 0;
		}
	}
	while (!s.empty()) {
		if (s.top() == '(' || s.top() == '[' || s.top() == ']' || s.top() == ')')
			return 0;

		ans += s.top() - '0';
		s.pop();
	}
	return ans;
}

int main() {
	string bracket;

	cin >> bracket;

	cout << check(bracket);
}

 

다른 사람 코드 참고해서 재도전

참고)) https://gpfatp.blogspot.com/2018/10/boj-2504.html

        https://hydroponicglass.tistory.com/1

그나마 내 코드와 비슷한 코드 참고해서!

 

#include <iostream>
#include <stack>
#include <string>

using namespace std;

//( : -1, ) : -2, [ : -3, ]: -4
int check(string str) {
	stack <int> s;
	int len = str.length();
	int temp = 0;
	int ans = 0;

	for (int i = 0; i < len; i++) {
		//열린 괄호인 경우
		if (str[i] == '(') s.push(-1);
		else if (str[i] == '[') s.push(-3);
		//닫힌 괄호인 경우
		else if (s.empty())  //1. 닫힌 괄호가 더 많은 경우
			return 0;
		else {
			if (s.top() == -1 && str[i] == ')') {
				s.pop();
				s.push(2);
			}
			else if (s.top() == -3 && str[i] == ']') {
				s.pop();
				s.push(3);
			}
			//s.top()이 숫자인 경우 또는 3. 괄호의 짝이 맞지 않는 경우
			else {
				temp = 0;
				while (s.top() != -1 && s.top() != -3) {
					temp += s.top();
					s.pop();

					if (s.empty())  //1.닫힌 괄호가 더 많은 경우
						return 0;
				}
				if (s.top() == -1 && str[i] == ')') {
					temp *= 2;
					s.pop();
				}
				else if (s.top() == -3 && str[i] == ']') {
					temp *= 3;
					s.pop();
				}
				else
					return 0;   //3. 괄호의 짝이 맞지 않는 경우

				s.push(temp);
			}
		}
	}

	while (!s.empty()) {
		if (s.top() == -1 || s.top() == -3) //2. 열린괄호가 더 많은 경우
			return 0;

		ans += s.top();
		s.pop();
	}
	return ans;
}

int main() {
	string bracket;

	cin >> bracket;
	cout << check(bracket);
}  

 

원리

입력 값 == (()[[]])([])

(

( (

( ( )  ->   ( 2

( 2 [

( 2 [ [

( 2 [ [ ]  ->  ( 2 [ 3

( 2 [ 3 ]  ->  ( 2 9

( 2 9 )  ->  (2 + 9) * 2 = 22

22 (

22 ( [

22 ( [ ]   ->  22 ( 3

22 ( 3 )  ->  22 6

답 = 22 + 6 = 28

 

<괄호의 짝이 맞지 않는 경우>

1. 닫힌 괄호왔는데 스택이 비어있는 경우(닫힌 괄호가 많다)

2. 반복문이 끝났는데 스택이 비어있지 않는 경우(열린 괄호가 많다)

3. 닫힌괄호와 열린괄호의 짝이 맞지 않는 경우

배운점

1. 막빠지에 계속 틀린 이유가 노직은 맞았는데 자료형 문제였다...(흐그...)

s.push(temp + '0');

ans += s.top() - '0';

이런식으로 char형과 int형을 혼합해서 썼더니 답에 오류가 생긴다.

c언어 할때는 큰 상관은 없었는데 확실히 백준 문제나 코딩 테스트때는 큰 자료형으로 통합해서 사용해야 한다.

두번째 참고사이트를 참고하여 괄호를 음수로 바꿔서 스택에 저장하였다.

 

---

다른 방법의 코드

이 코드에 대한 공부가 더 필요하다!

원리

입력 값 == ( ( ) [ [ ] ] )

temp = 1;

(   -> temp = 2

( (  -> temp = 2 * 2

( ( ) ->  result = 2 * 2, temp = 2  

( [   ->  temp = 2 * 3

( [ [   ->  temp = 2 * 3 * 3

( [ [ ]  ->  result = 2 * 2 + 2 * 3 * 3, temp = 2 * 3

( [ ] ->  result = 2 * 2 + 2 * 3 * 3 + 2 * 3, temp = 2

( )  ->  result = 2 * 2 + 2 * 3 * 3 + 2 * 3 + 2, temp = 1

 

https://dntworry-behappy.tistory.com/8

[C++] 백준 2504번 - 괄호의 값

https://jaimemin.tistory.com/820

백준 2504번 괄호의 값