[BOJ 2504번] 괄호의 값

이번문제는 스택 괄호쌍의 응용으로 쉽지 않은 문제였다.

다른 사람의 풀이 설명은 알고리즘이 동작하는 것 위주로 설명하는데 나로서는 쉽게 받아들여지지 않았다.

단순히 이 알고리즘 풀이만 외운다면 이 문제야 풀수 있겠지만 응용력은 기를수 없어보였다.

항상 어떤 문제를 풀때 아이디어가 뭐고 어떻게 발상했는지를 모르면 다른문제에 적용을 할수가 없어서

나는 내 언어로 완전히 바꾸고 이해를 해야 하는 타입이였다. 그래야만 한문제를 풀어도 열문제를 푼 효과를 얻을수 있기 때문이다.

모르는 문제를 답지를 보고 풀고 그 아이디어를 제대로 배웠다면 수십가지의 응용들도 해결할 능력을 얻기 때문에

모르는 것 위주로 문제를 풀어야하고 그게 좋은 방향인걸을 스스로 잘 알지만 역시 문제 앞에서 지고 말았다는 생각이 들어 항상 기분이 좋지가 않았다. 하지만 블로그에 내가 모르는것 문제에 대해 포스팅을 하게된다면 훨씬 더 정리가 잘되기도 하고 기억에도 잘 남겠지만 무엇보다도 모르는것에 대해 두려워 하지 않고 내가 블로그에 정리해서 너같은 문제들을 정복해주마 같은 덤벼드는 마인드가 생기게 되어 오히려 승부욕이 타오르게 되고 이것이 블로그의 순기능이 아닐까 싶다.

앞으로 알고리즘 포스팅이 올라온다면 이 게시물들은 내가 못푼 문제들로 구성될것이다. ㅋㅋ 

 

먼저 괄호를보고 스택을 발상하는데는 어려움이 없었지만 배율이 중첩되고 더하기도 되는 상황에서 헷갈리기 시작했다.

의외로 해결법은 단순했는데 바로 수학의 분배법칙이 전부고 나머지는 약간의 테크닉이였다.

분배법칙은 각개전투라고 할수있다. 

아무리 복잡해 보여도 현재까지의 배율을 알고있고 여러 덧셈을 생각하지말고 한개에 대해서만 각개전투로 배율을 적용하고 그 각각 숫자들을 그냥 한곳에 더해주기만 하면 문제해결이다. 한개에 대한 배율적용이 끝나면 배율을 다시 줄여주는 작업만 잊지 않는다면 크게 실수할 부분이 없어보인다. 

 

즉 현재까지의 배율을 기억해줄 rate와 각각 한개의 값을 더해줄 sum 만 따로 관리해주는 약간의 테크닉을 해주면 끝이다.

자세한 코드는 주석을 확인하면된다.

 

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

stack<char> s;
string str;

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

  cin >> str;
  int sum = 0; // 누적해서 더해질 값
  int rate = 1; // 현재 배율

  for(int i = 0; i < str.size(); i++){
    if(str[i] == '('){
      rate *= 2; // 소괄호가 나오면 곱해질 값 2배 증가
      s.push(str[i]);
    }
    else if(str[i] == '['){
      rate *= 3; // 대괄호가 나오면 곱해질 값 3배 증가
      s.push(str[i]);
    }
    else if(str[i] == ')'){
      if(s.empty() || s.top() != '('){
        cout << 0;
        return 0;
      }
      if(str[i-1] == '(') sum += rate; // 직전 괄호가 여는 괄호였다면 sum에 값 추가
      s.pop();
      rate /= 2; // 소괄호 쌍이 사라졌으니 배율 조정      
    }
    else{ // str[i] == ']'
      if(s.empty() || s.top() != '['){
        cout << 0;
        return 0;
      }
      if(str[i-1] == '[') sum += rate; // 직전 괄호가 여는 괄호였다면 sum에 값 추가
      s.pop();
      rate /= 3; // 대괄호 쌍이 사라졌으니 배율 조정
    }
  }
  if(s.empty()) cout << sum;
  else cout << 0;
}