문제 출처

1. 문제설명

  • 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열
  • 올바른 괄호열 정의
    • 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’
    • 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열
    • X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열
  • 괄호열 값 구하는 방법
    • ‘()’ 인 괄호열의 값은 2
    • ‘[]’ 인 괄호열의 값은 3
    • ‘(X)’ 의 괄호값은 2×값(X)
    • ‘[X]’ 의 괄호값은 3×값(X)
    • 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y)



2. 알고리즘 설계

  • 스택을 활용한 문제이다.
    • 연속된 괄호들 사이에서 값이나 부정한 조건을 탐색하는 문제는
    • 거의 스택 문제인 거 같다.
  • 여는 괄호를 만났다면 정답값에 2 또는 3을 곱해주고 push
  • 닫는 괄호를 만났다면,
    • 스택이 비어있거나, 스택의 top이 다른 여는 괄호라면
      • 종료
    • 그렇지 않다면, 2 또는 3으로 나눠주고 pop
      • 만약 이전 인덱스의 괄호가 동일한 여는 괄호라면, 현재 숫자를 정답값에 더한다.
  • 앞서 설명한 로직은 괄호열 값 구하는 방법의 조건을 구현한 것이다.



3. 전체 코드

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int num = 1, ans = 0;
	string str;
	cin >> str;

	stack<char> st;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			num *= 2;
			st.push('(');
		}
		else if (str[i] == '[') {
			num *= 3;
			st.push('[');
		}

		else if (str[i] == ')') {
			if (st.empty() || st.top() != '(') {
				cout << "0";
				return 0;
			}

			if (str[i - 1] == '(') ans += num;
			num /= 2;
			st.pop();
		}
		else {
			if (st.empty() || st.top() != '[') {
				cout << "0";
				return 0;
			}

			if (str[i - 1] == '[') ans += num;
			num /= 3;
			st.pop();
		}
	}

	if (!st.empty()) cout << "0";
	else cout << ans;
}



4. 소감

  • 처음에 다음과 같은 if문을 하나의 if문으로 처리했다.
	else if (str[i] == ')') {
		if (st.empty() || st.top() != '(')

	// 기존
	else if (str[i] == ')' || st.empty() || st.top() != '(')
  • 세 가지 조건 중 하나만 통과되도 해당 if문에 들어가기 때문에 주의하자.