[BOJ] 2504번 - 괄호의 값 (Swift, C++)

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

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

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

 

<문제 링크>

2504번: 괄호의 값

---

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

---

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

---

문제 풀이

이 문제는 이전에 다뤘던 문제와 유사한 형식입니다. 

이는 괄호와 관련된 문제로, 괄호들이 특정 조건에 맞게 구성되어야 합니다. 

따라서 괄호를 스택에 저장하고, 괄호의 쌍이 올바르게 구성되어 있는지 확인합니다.

 

이 문제는 또한, 괄호 내부에 있는 괄호 쌍이 의미하는 계산 과정을 먼저 해결해야 합니다. 

예를 들어, [()()]의 경우에는 [] 안에 있는 계산이 먼저 이루어져야 합니다.

[2 + 2]

3 * 4

12

 

이 과정은 앞서 등장하는 곱해져야 할 값들을 누적하여 곱한 후, 해당 괄호가 누적 곱에 미치는 영향이 끝나면 나눗셈을 통해 제거합니다.

만약, 열린 괄호 다음에 닫힌 괄호가 오면 해당 누적 곱을 정답 변수에 더해줍니다.

 

 

예를 들어, (([]))가 주어졌을 때를 생각해봅시다.

 

해당 문자열을 순회하면 처음으로 오는 문자는 '('이고, 누적 곱은 2가 됩니다.

 

다음 문자는 또 '('이고 누접 곱이 2*2로 4가 됩니다.

 

다음은 '['이 오고 누적 곱은 2*2*3=12가 됩니다.

 

이어서 닫힌 괄호 ']'가 오면 누적 곱을 정답 변수에 더하고 해당 괄호의 영향을 누적 곱에서 제거합니다.

2 * 2 * 3 = 12

12 / 3 = 4

 

다음으로는 또 닫힌 괄호가 오며, 이전 괄호가 열린 괄호가 아닌 닫힌 괄호이므로

정답 변수에 값을 더해주지 않고 누적 곱에서 영향만 지워줍니다.

2 * 2 * 3 = 12

12 / 3 = 4

4 / 2 = 2

 

위와 동일합니다.

2 * 2 * 3 = 12

12 / 3 = 4

4 / 2 = 2

2 / 2 = 1

 

결론적으로, 열린 괄호 다음에 닫힌 괄호가 오면 정답 변수에 누적 곱을 더하고, 괄호에 따라 누적 곱 변수를 곱하고 나누어주면 됩니다. 

이해가 어렵다면 아래 정답 코드를 확인해보세요!

풀이 순서

1. 입력 값으로 받은 문자열로 순회를 돈다

2. 순회를 도는 문자로 분기 처리를 해준다.

2-1. 해당 문자가 열린 괄호일 경우, 누적 곲에 해당 괄호의 영향을 주는 값을 곱해준다.

2-2. 해당 문자가 닫힌 괄호일 경우, 괄호가 놓일 수 있는 조건이 맞는 지 먼저 확인해주고 맞다면 이전 괄호에 따라 조건을 처리해준다.

3. 정답을 출력한다.

---

풀이 코드

< Swift>

// Swift
let str = readLine()!

var s = [Character]()

var ans = 0
var n = 1  // 곱해지는 값

var prev: Character = " "  // 반복문의 직전 문자 저장

for c in str {
    if c == "(" {
        n *= 2
        s.append(c)
        
    } else if c == "[" {
        n *= 3
        s.append(c)
        
    } else if c == ")" {
        
        if s.isEmpty || s.last != "(" {
            s.append(" ")  // 정답 출력 시, 스택의 빈배열 분기처리로 정답을 한 번만 출력하기 위함
            break
            
        } else if prev == "(" {
            ans += n
            n /= 2
            s.removeLast()
            
        } else { // 경우: 닫 -> 닫
            s.removeLast()
            n /= 2
        }
        
    } else {  // c == "]'
        if s.isEmpty || s.last != "[" {
            s.append(" ")
            break
        } else if prev == "[" {
            ans += n
            n /= 3
            s.removeLast()
        } else { // 경우: 닫 -> 닫
            s.removeLast()
            n /= 3
        }
    }
    
    prev = c  // 직전 문자 기록
}

if s.isEmpty {
    print(ans)
} else {
    print(0)
}

---

< C++>

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

stack<char> s;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string str;
    cin >> str;
    
    int ans = 0;
    int n = 1;
    
    for(int i = 0; i < str.size(); i++){
        if(str[i] == '('){
            n *= 2;
            s.push(str[i]);
        }
        else if(str[i] == '['){
            n *= 3;
            s.push(str[i]);
        } 
        else if(str[i] == ')'){
            if(s.empty() || s.top() != '('){
                cout << 0;
                return 0;
            }
            if(str[i-1] == '(') ans += n;
            n /= 2;
            s.pop();
        }
        else{ // ']'
            if(s.empty() || s.top() != '['){
                cout << 0;
                return 0;
            }
            if(str[i-1] == '[') ans += n;
            n /= 3;
            s.pop();
        }
    }
    if(s.empty()) cout << ans;
      else cout << 0;
}

---

마무리

괄호와 관련된 문제는 스택을 사용하여 해결해야 함을 깨달았습니다. 

그러나 괄호 내부에 있는 계산 과정을 해당 괄호보다 먼저 처리해야 하기 때문에 

이 부분을 다루는 것이 꽤 어려웠습니다. 

 

이 문제를 해결하기 위해, 누적 곱 개념을 도입하여 계속해서 영향을 주는 값을 저장하고 

이를 이용하여 정답을 처리해 주었습니다.