[백준/boj] 2504번: 괄호의 값 | C++

 

 

---

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

2504번: 괄호의 값

문제풀이 핵심

현재 괄호에서 연산을 해야하는 숫자가 몇개인지를 파악하기 위해, 현재 괄호가 열리는 시점에서 이미 존재하고있는 값(괄호 밖에 존재하는 값)이 몇개인지 알아보기 위해 숫자를 담는 스택(x)의 사이즈를 따로 mess 라는 스택에 저장준다.

 

이때 mess 값을 int 로 하는 것이 아닌 stack<int> 로 선언해주는 것이 핵심이었다. 

그렇게 하면 순서대로 mess 값을 저장해뒀다가 괄호 하나가 닫힐 때 마다 mess값을 pop 하여 연산 순서에 맞게 mess 값을 사용할 수 있었다. 

 

mess 는 괄호 내 연산에서 아래와 같이 사용된다.

int q = x.size()-mess.top(); //반복 횟수

int result=0;

while(q--){ // 괄호 안에 q개의 값들이 나란히 있는 경우 처리 

int c=x.top(); 

x.pop();

result += c;

}

 

mess.pop();

x.push(result*3);

 

---

문제풀이 코드

#include<iostream>
#include<stack>

using namespace std;

string a;
stack<char> s; // 여는 괄호 저장
stack<int> x; // 계산된 값 순서대로 저장
stack<int> mess;
int fin;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> a;
    mess.push(0);

    for(int i =0;i<a.length();i++){ //왼쪽부터 각 괄호가 무엇인지 확인
        char cur = a[i]; //현재 괄호 받을 변수
        if(cur == '('||cur =='['){
            s.push(cur);
            if(i>0){
                if(a[i-1]=='('||a[i-1]=='['){
                    mess.push(x.size());
                }
            }

        }else if(cur == ')'){
            if(!s.empty()&&s.top() == '['){
                cout <<'0'<<'\n';
                return 0;
            }else if(s.empty()){
                cout <<'0'<<'\n';
                return 0;
            }

            if(s.top()==a[i-1]){
                x.push(2);
                s.pop();

            }else{
                s.pop();

                int q = x.size()-mess.top();
                int result=0;
            
                while(q--){
                    int c=x.top();
                    x.pop();
                    result += c;
                }
                x.push(result*2);
                mess.pop();

            }
        }else { // cur == ']'
            if(!s.empty()&& s.top() == '('){
                cout <<'0'<<'\n';
                return 0;
            }else if(s.empty()){
                cout <<'0'<<'\n';
                return 0;
            }

            if(s.top()==a[i-1]){
                x.push(3);
                s.pop();
            }else{
                s.pop();
                
                int q = x.size()-mess.top();
                int result=0;

                while(q--){
                    int c=x.top();
                    x.pop();
                    result += c;
                }  
                mess.pop();
                x.push(result*3);
            }
        }
    }
    
    if(!s.empty()){
        cout <<'0'<<'\n';
        return 0;
    }
    while(!x.empty()){
        int q = x.top();
        x.pop();
        fin +=q;
    }
    cout <<fin;
    return 0;
}

 

---

로직 설명

 

괄호가 닫힐 때 마다 ()와 []는 숫자로 바꾸어 별도의 스택(x)에 저장하고, 괄호 속 괄호값 or 나란히 존재하는 괄호값에 대해서는 연산을 진행한다. 연산 후 나온 결과는 x에 저장한다. 이때 x에는 현재 괄호에서 사용될 값과, 현재 괄호 밖에 존재해 연산에서 제외되어야 하는 값이 존재한다.

현재 사용할 값이 얼마만큼인지를 알 수 있는 방법으로 괄호가 겹쳐서 열릴때마다 ||  ex ((,([,[(,[[   || mess 라는 변수로 이미 x 에 존재하는 값의 개수(x의 크기), 즉 현재의 괄호 밖에 존재해 괄호 내 연산에서 제외되어야 하는 값의 개수를 알아낸다. 이때 이 mess 는 단순 int 가 아닌 stack int이다.

가장 최근의 mess 값을 pop해주어 연산이 실행될 때의 x.size - mess 만큼 반복을 돌아 x에서 값을 빼주고 빼낸 값은 더하기 연산을 시행하게 된다. 더하기 연산을 시행한 후 나온 값은 다시 x에 넣어준다.

 

---

 

마무리

다른 분들 풀이를 보니 70줄 내외이더라..내 코드는 100줄 정도인데..

조금 더 효율적인 풀이를 고민해봐야겠다