[백준 2504] - 괄호의 값

 

문제

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

 

입력

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

 

출력

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

 

솔루션

• 자료구조 스택을 이용했다.
• 문제를 풀기 위해 분배 법칙을 이용했다.
  
  • 아래 예시를 보자.
  • 2 * (3 + 4 * 3) 이라는 식이 있을 경우, 이를 분배해서 나열해보면 다음과 같을 것이다.
    • 2 * 15 (X) 
    • 6 + 24 (O)
  • 계산식 괄호가 닫혔을 때 (')', ']') 계산을 하는 것이 아니라 각각 따로 계산을 한 뒤 중간 값인 6과 24를 따로 구해서 계산한다고 생각하면 된다.
• 문제의 예시를 보자.
  • 중간 값을 계산하기 위한 공간을 마련한다 (아래 코드의 경우 temp). 
  • 먼저 왼쪽 괄호 ('(', '[') 일 경우, 계산 없이 temp에 2 또는 3을 곱하고, 괄호를 스택에 삽입한다 (Push).
  • 오른쪽 괄호 (')', ']') 일 경우, 몇 개의 조건을 검사한다.
    • 1. 스택이 비어있는지 확인한다.
      • 오른쪽 괄호가 나왔을 때 스택이 비어있다면, 이는 올바른 괄호 쌍이 아니므로 0을 반환하면 된다.
    • 2. 각 괄호 쌍이 맞는지 확인한다 ('[' - ']', '(' - ')').
      • 여기서 중요한 것이 있는데, 현재 오른쪽 괄호가 이와 쌍이 맞는 왼쪽 괄호라면, 바로 직전의 괄호를 확인한다.
        • 만약 직전 괄호가 오른쪽 괄호 (')', ']') 라면, 바로 직전에 이미 중간값을 계산하고 더했다는 의미이므로 temp를 각 값 2 또는 3을 나눈다.
        • 그런 다음, 스택의 맨 꼭대기 왼쪽괄호를 빼낸다 (Pop).
      • 괄호쌍이 맞지 않다면, 마찬가지로 올바른 괄호 쌍이 아니므로 0을 반환한다.
  • 이를 괄호 문자열 끝까지 진행하면 된다.
• 아래는 대략적인 계산 과정을 그림으로 표현한 것이다.

 

Code

• 전체 코드 : Solution_2504

public int solution(String str) {
    Stack<Character> pair = new Stack<>();
 
    char[] ctr = str.toCharArray();
    boolean err = false;
    int sum = 0, temp = 1;
 
    for (int i = 0; i < ctr.length && !err; i++) {
 
        switch (ctr[i]) {
        case '[':
            pair.push(ctr[i]);
            temp *= 3;
            break;
        case '(':
            pair.push(ctr[i]);
            temp *= 2;
            break;
        case ']':
            if (pair.isEmpty()) {
                err = true;
                sum = 0;
                continue;
            }
 
            if (pair.peek() == '[') {
                if(ctr[i - 1] != ']' && ctr[i - 1] != ')')
                    sum += temp;
                pair.pop();
            } else {
                err = true;
                sum = 0;
                continue;
            }
            
            temp /= 3;
            break;
        case ')':
            if (pair.isEmpty()) {
                err = true;
                sum = 0;
                continue;
            }
 
            if (pair.peek() == '(') {
                if(ctr[i - 1] != ']' && ctr[i - 1] != ')')
                    sum += temp;
                pair.pop();
            } else {
                err = true;
                sum = 0;
                continue;
            }
            
            temp /= 2;
            break;
        }
    }
 
    if (!pair.isEmpty())
        sum = 0;
    
    return sum;
}

 

결과