2504. 괄호의 값 (C++)

 

한 3일 걸린 듯 하다..끝끝내 혼자 힘으로 풀지는 못했다.. 거의 다 왔는데 항상 이런다..

 

암튼 이 알고리즘을 생각하기가 너무 어려웠다.

 

괄호마다 곱하는 수도 다르고 닫는 위치에 따라 더할지 곱할지가 정해지니 머리가 터질 지경이었다.

 

알고리즘은 다음과 같다.

1) 왼쪽 괄호가 나올 때마다 스택에 넣는다.

tmp를 선언하고 소괄호가 나올 때엔 2를 곱하고 대괄호가 나올 때엔 3을 곱한다.

tmp 는 0으로 초기화하는것이 아닌 1로 초기화를 해줘야 한다. 곱하기는 0과 곱하면 무조건 0 이지않은가.

2) 출력의 문구에서 볼 수 있듯이 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다고 했다. 그래서 그 조건문 또한 bool로 구분하여 추가했다.

3) 오른쪽 괄호가 나올경우 스택에서 뺀다.

3-1 이때 바로 전 인덱스의 괄호가 현 인덱스와 쌍일 경우에 tmp의 값을 더해준다.

3-2 tmp 값을 소괄호일경우 2로 나누고 대괄호일 경우 3으로 나눠준다.

4) 2에서 추가해준 bool과 s.empty() 를 이용하여 스택이 비어있지 않을 경우 올바르지 않은 괄호이기 때문에 0을 출력해주는 구문과, 모든 조건을 충족할 경우 총 더해준 result 값을 출력해준다.

 

음..이해가 안간다면 이 분의 블로그를 참고하자.

jaimemin.tistory.com/820

백준 2504번 괄호의 값

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	stack<char> s;
	string text;
	long long result = 0;
	int tmp = 1;
	bool impossible = false;
	
	cin >> text;
	for(int i = 0; i < text.size(); i++) {
		if(text[i] == '(') {
			tmp *= 2;
			s.push(text[i]);
			
		}
		else if(text[i] == '[') {
			tmp *= 3;
			s.push(text[i]);
			
		}
		else if(text[i] == ')' && (s.empty() || s.top() != '(')) {
			impossible = true;
			break;
		}
		else if(text[i] == ']' && (s.empty() || s.top() != '[')) {
			impossible = true;
			break;
		}
		else if(text[i] == ']') {
			if(text[i-1] == '[') {
				result += tmp;
			}
			s.pop();
			tmp /= 3;
		}
		else if(text[i] == ')') {
			if(text[i-1] == '(') {
				result += tmp;
			}
			s.pop();   
			tmp /= 2;
		}
	}

	
	if(impossible || !s.empty()) {
		cout << "0" << endl;
	} else {
		cout << result << endl;
	}
}

이 문제는 나중에 또 해봐야 겠다.