[백준] 괄호의 값 2504

문제

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

• 입력이 잘못된 괄호열이면 0을 출력한다.
• 괄호열을 계산한 값을 출력하라.

입력

(()[[]])([])

()[[]] : 2+33=11
(()[[]]) : 2×11=22
([]) : 23=6
전체 괄호 값 : 22+6 = 28

풀이

풀이 1

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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin>>str;
    
    stack<char> st1;
    stack<char> st2;
    
    int isTwoOpen =0;
    int isThreeOpen=0;
    
    for(auto c:str){
        if(c=='(') {
            st1.push(c);
            isTwoOpen=1;
        }
        else if(c=='['){
            st1.push(c);
            isThreeOpen=1;
        }
        else if(c==')' && st1.top() == '('){
            if(isTwoOpen){//열리자마자 바로 닫는것
                sum+=2;
            }
            else sum = sum*2
        }
        
        
    }
    
    return 0;
}

풀이 2 ***

곱하는 것과 더하는 것을 어떻게 구분할지 헷갈린다..
다른 블로그를 참조해보니 분배 법칙을 사용해서 문제를 풀 수 있다.
2(2+3*3) + 2 * 3 -> 2*2 + 2*3*3 + 2*3
이렇게 분배해서 로직을 짤 수 있다.

temp : answer에 더하기 전 중간값을 계산하기 위한 변수 (곱셈)

1. '('인경우
   temp에 2를 곱하고 스택에 '(' push
2. ')' 인경우
   1) 스택이 비어있거나 s.top() !='(' 이면 wrong -> answer =0;
   2) 이전 문자가 '('인 경우
   바로 닫히는 것이기 때문에 () temp값을 answer에 더해주고 temp를 2로 나눈다.
   s.pop() //ans = 2*2 temp=2
   3) 이전 문자가 '('이 아닌 경우
   바로 닫히는 것이 아니기 때문에 ( answer값이 이미 더해져 있는 상태이다.
   따라서 temp를 2로 나누고 s.pop() //temp =1,

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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin>>str;
    int ans=0;
    
    stack<char> s;
    int tmp=1;
    
    bool istwoOpen  = false;
    bool isThreeOpen =false;
    
    // (() [[]] ) ([])
    for(auto c:str){
        if(c=='('){
            tmp *=2; //2 4
            s.push(c); //( 
            istwoOpen=true;
        }
        else if(c=='['){
            tmp *=3;
            s.push(c);
            isThreeOpen=true;
        }
        
        else if(c==')'){
            if(s.empty() || s.top()!= '('){ans =0; break;}
            if(s.top() == '('){
                if(istwoOpen){//() 바로 닫히는 것은 더하기
                    ans +=tmp;//4
                    tmp/=2; //2
                    s.pop();
                    istwoOpen=false;
                }
                else{ //(())
                    //이미 ans에 값이 더해져있음
                    tmp /=2; 
                    s.pop();
                }
            }
            
        }
        
        else if(c==']'){
            if(s.empty() || s.top()!= '['){ans =0; break;}
            if(s.top() == '['){
                if(isThreeOpen){
                    ans +=tmp;
                    tmp/=3;
                    s.pop();
                    isThreeOpen=false;
                }
                else{ 
                    //이미 ans에 값이 더해져있음
                    tmp /=3; 
                    s.pop();
                }
                
            }
            
        }
        
    }
    if(!s.empty()) ans =0;
    cout << ans;
    
    return 0;
}

• 예제1에서 30이 나온다...
• [가 열렸을 때 (가 닫히는 것으로 바꿈

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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin>>str;
    int ans=0;
    
    stack<char> s;
    int tmp=1;
    
    bool istwoOpen  = false;
    bool isThreeOpen =false;
    
    // (() [[]] ) ([])
    for(auto c:str){
        if(c=='('){
            tmp *=2; //2 4
            s.push(c); //( 
            istwoOpen=true;
            isThreeOpen =false;
        }
        else if(c=='['){
            tmp *=3;
            s.push(c);
            isThreeOpen=true;
            istwoOpen  = false;
        }
        
        else if(c==')'){ 
            if(s.empty() || s.top()!= '('){ans = 0; break;}
            if(s.top() == '('){
                if(istwoOpen){//() 바로 닫히는 것은 더하기
                    ans +=tmp;//4
                }
                s.pop();
                istwoOpen=false;
                isThreeOpen=false;
                tmp/=2; //괄호 쌍이 사라졌으니 2로 나눔
            }
            
        }
        
        else if(c==']'){
            if(s.empty() || s.top()!= '['){ans =0; break;}
            if(s.top() == '['){
                if(isThreeOpen) ans +=tmp;
                s.pop();
                isThreeOpen=false;
                istwoOpen=false;
                tmp/=3;
            }
        }
        
    }
    if(!s.empty()) ans =0;
    cout << ans;
    
    return 0;
}

-> 예제는 맞는데 제출하니 틀렷다!!!
출력 오류..ㅎㅎ

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

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin>>str;
    int ans=0;
    
    stack<char> s;
    int tmp=1;
    
    bool istwoOpen  = false;
    bool isThreeOpen =false;
    
    // (() [[]] ) ([])
    for(auto c:str){
        if(c=='('){
            tmp *=2; //2 4
            s.push(c); //( 
            istwoOpen=true;
        }
        else if(c=='['){
            tmp *=3;
            s.push(c);
            isThreeOpen=true;
        }
        
        else if(c==')'){
            if(s.empty() || s.top()!= '('){cout<<0; break;}
            if(s.top() == '('){
                if(istwoOpen){//() 바로 닫히는 것은 더하기
                    ans +=tmp;//4
                }
                s.pop();
                istwoOpen=false;
                tmp/=2; //괄호 쌍이 사라졌으니 2로 나눔
            }
            
        }
        
        else if(c==']'){
            if(s.empty() || s.top()!= '['){ans =0; break;}
            if(s.top() == '['){
                if(isThreeOpen) ans +=tmp;
                s.pop();
                isThreeOpen=false;
                tmp/=3;
            }
        }
        
    }
    if(!s.empty()) ans =0;
    cout << ans;
    
    return 0;
}

풀이 4 - 배열사용

#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 num = 1; // 곱해질 값

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

참고

https://mjmjmj98.tistory.com/70