백준, BOJ, 2504번, 괄호의 값 C++ [CPP]

 

어렵지 않지만 생각을 잘해야 하는 문제

 

220227에 다시 풀어보니 생각이 안나는 어려운 문제.. 거의 일년만에 다시 푸네..

ㅋㅋㅋㅋㅋ 값이 확정되는 때가 언제더라 생각하고 있었다.

 

www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

---

 

괄호가 나왔으니

스택에 쌓아가면서 할 것이란 것은 예상을 했다.

하지만 또 문제였던 것이

 

괄호를 닫을 때 이것이 멀리 있는 괄호가 닫히는 것인지

가까이 있는 괄호가 닫히는 것인지 구분을 하지 못한다는 큰 맹점이 생긴다.

 

EX) ()도 닫힌것요 (())도 닫힌 것이니라. 

스택에서는

( -> () -> ""

( -> () -> "" -> ( -> () -> ""

이니라.

 

스택에선 구분할 수가 없다고 하니라.

 

나는 이전의 문제를 풀고도.. 이 처리 방법에 애를 먹었다.

 

또한 올바르지 않은 입력에 대해서는 check 변수를 두어 항상 검사하게 하였다.

닫는 괄호가 스택에 들어왔을 때

 

스택이 비어있거나, 여는 괄호 짝이 없거나

또는 모든 입력을 받았음에도 스택이 비어있지 않았다면

 

올바르지 않은 입력을 받은 것이다.

 

다시 본론으로 돌아와서 결정해야 한다.

모두다 입력받은 뒤 스택을 빼면서 결정할 것인가?

입력받으면서 값을 결정할 것인가?

-> 문자열의 길이가 최대 30이기에 어차피 무엇인가에 제한에 걸리지 않을 것임은 분명했다.

 

하지만 거꾸로 한다고 쉬워질 것같지는 않기에

시간복잡도 상 입력받으면서 값을 결정하는 것이 쉽다고 판단했다.

 

처음에는 값을 임시 저장해서 풀려고 했다.

#1 시도는 박살났다.

 

그래서 다음에는 생각해봤다.

분배법칙으로 풀면 될 것 같은데??

(()[[]]) 값은 22다

값이 나온 경위는

2*(2 + 3*(3)) 이다.

( 이 안에 있는 것들은 2배가 되겠구나

(( 이 안에 있는 것들은 4배가 되겠구나

(() 값이 나왔구나 우선 4를 넣자, 그리고 그 뒤에 것들은 2배가 되겠구나

(()[ 이 안에 있는 것들은 6배가 되겠구나

(()[[ 이 안에 있는 것들은 18배가 되겠구나

(()[[] 값이 나왔구나 우선 18를 넣자, 그리고 그 뒤에 것들은 6배가 되겠구나

************ 여기가 중요하다.

(()[[]]

값이 나왔구나? -> 라고 인식이 안된다. 멀리 있는 기호임에도 값이 나온 것으로 판단이 되어버린다.

그렇다고 6을 넣어버리면 틀린 계산이 되어버린다.

값이 나오는 경우는 괄호가 닫혔을 때가 아니라

[] 가 붙어나올 때 이다.

그러므로 해당 닫는 괄호가 나왔을 때!

해당 괄호의 앞 문자가 여는 괄호일 경우에만 값이 나온다라고 판단해야 한다는 말이다.

-> 해당 닫는 괄호는 [] 처럼 바로 가까이서 닫는 괄호이니라.

 

괄호에서 꼬아서 나올 것은 여기서 다 응용된다.

"멀리 있는 괄호와 가까이 있는 괄호를 구분할 수 있느냐?"

************

 

다시 본론으로

(()[[]] -> 앞의 문자열을 조사해보니 값이 나온 것은 아니구나,  그 뒤에 것들은 2배가 되겠구나.

(()[[]]) -> 앞의 문자열을 조사해보니 값이 나온 것은 아니구나, 그 뒤에 것들은 1배가 되겠구나.

 

 

4+ 18 =  2*2 + 2*3*3

22 완성

 

#2에서 해당 알고리즘을 구현했다.

 

 

---

 

 

#1 나의 첫번째 풀이

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

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    getline(cin, s);
    stack<char> stk;
    
    
    int sum = 0;
    int a = 0;
    int b = 0;
    
    bool check = true;
    for(int i = 0; i<s.length(); i++){
        
    
        
        if(s[i] == '('){
            a = 0;
            stk.push(s[i]);
        }else if(s[i] == ')'){
            //올바르지 못한 입력
            if(stk.empty() || stk.top() != '('){
                check = false;
                break;
            }
            stk.pop();
            // 비어있으면
            if(stk.empty()){
                sum += 2*b;
            }
            else if(a == 0){
                a = 2;
                b += a;
            }else{
                b -= a;
                a *= 2;
                b += a;
            }
            
            if(stk.empty()){
                sum += 2*b;
            }
        }else if(s[i] == '['){
            a = 0;
            stk.push(s[i]);
        }else if(s[i] == ']'){
            //올바르지 못한 입력
            if(stk.empty() || stk.top() != '[' ){
                check = false;
                break;
            }
            stk.pop();
            // 비어있으면
            if(stk.empty()){
                sum += 3*b;
            }
            if(a == 0){
                a = 3;
                b += a;

            }else{
                b -= a;
                a *= 3;
                b += a;
            }
        }
    }
    
    //
    if(check == false){
        cout << '0';
    }else{
        cout << sum;
    }
    
}

 

#2 맞은 풀이

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    getline(cin, s);
    stack<char> stk;


    int sum = 0;
    int temp = 1;

    bool check = true;
    //분배법칙으로 풀어보자.
    for (int i = 0; i < s.length(); i++) {


        if (s[i] == '(') {
            stk.push(s[i]);
            temp *= 2;
        }
        else if (s[i] == ')') {
            //올바르지 못한 입력
            if (stk.empty() || stk.top() != '(') {
                check = false;
                break;
            }
            //올바른 입력
            else {
                //이 조건이 나오는 이유가 중요함.
                // '여는 괄호가 직전에 있지 않으면 값이 되는 것이 아님'
                if(s[i-1] == '('){
                    sum += temp;
                }
                stk.pop();
                temp /= 2;

            }
        }
        else if (s[i] == '[') {
            stk.push(s[i]);
            temp *= 3;
        }
        else if (s[i] == ']') {
            //올바르지 못한 입력
            if (stk.empty() || stk.top() != '[') {
                check = false;
                break;
            }
            // 올바른 입력
            else {
                //이 조건이 나오는 이유가 중요함.
                if(s[i-1] == '['){
                    sum += temp;
                }
                stk.pop();
                temp /= 3;

            }
            
        }
    }

    //
    if (check == false || !stk.empty()) {
        cout << '0';
    }
    else {
        cout << sum;
    }

}

 

---

 

# 220227 나의 풀이

#include <bits/stdc++.h>

using namespace std;

string s;

int answer, temp;
int main(){
    cin >> s;
    bool check = true; //올바른 괄호인가?
    
    temp = 1;
    stack <char> stk;
    
    //열리는 괄호가 나타나는 순간 그 안의 모든 것들은 ( 2배, [ 3배가 된다.
    
    //값은 직전에 닫힐 때만 확정된다.
    //-> stack에서 빠져나갈 때가 아니라 ()처럼 붙어있는 괄호에서만 그렇다.
    
    //모든 괄호 대입
    for(int i = 0; i<s.size(); i++){
        
        //1
        if(s[i] == '('){
            temp *= 2;
            stk.push('(');
        }
        //2
        else if(s[i] == ')'){
            if(stk.empty()){check = false; break;}
            if(stk.top() == '(' && s[i-1] == '('){
                answer += temp;
                temp /= 2;
                stk.pop();
            }else if(stk.top() == '('){
                temp /= 2;
                stk.pop();
            }else{
                check = false;
                break;
            }
        }
        //3
        else if(s[i] == '['){
            temp *= 3;
            stk.push('[');
        }
        //4
        else if(s[i] == ']'){
            if(stk.empty()){check = false; break;}
            if(stk.top() == '[' && s[i-1] == '['){
                answer += temp;
                temp /= 3;
                stk.pop();
            }else if(stk.top() == '['){
                temp /= 3;
                stk.pop();
            }else{
                check = false;
                break;
            }
        }
    }
    
    //올바른 괄호면 당연히 스택 비어있음.
    if(check && stk.empty()){
        cout << answer;    
    }else{
        cout << 0 ;
    }
    
    
    return 0;
}