2504번 - 괄호

2504번: 괄호의 값 (acmicpc.net)

위 문제를 풀어보았다. 아래와 같은 조건으로 최종 값을 계산하는 문제다

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
6. 유효한 괄호열이 아니면 0을 출력한다

Stack을 이용해 괄호 문제를 푸는 경험은 많이 해봤으나, 이번 문제는 조금 더 독특했다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        Stack<Integer> stack = new Stack<>();
        int[] sumList = new int[30];
        Arrays.fill(sumList, 1);
        int count = 0;

        for (int i = 0; i < input.length(); i++) {
            char bracket = input.charAt(i);
            if (bracket == '(') {
                stack.add(2);
                count++;
            } else if (bracket == '[') {
                stack.add(3);
                count++;
            } else if (bracket == ')') {
                if (stack.isEmpty() || stack.pop() != 2) {
                    System.out.println(0);
                    System.exit(0);
                }
                count--;
                if (sumList[count] == 1) {
                    sumList[count] = 2 * sumList[count + 1];
                    sumList[count + 1] = 1;
                } else {
                    sumList[count] += 2 * sumList[count + 1];
                    sumList[count + 1] = 1;
                }
            } else {
                if (stack.isEmpty() || stack.pop() != 3) {
                    System.out.println(0);
                    System.exit(0);
                }
                count--;
                if (sumList[count] == 1) {
                    sumList[count] = 3 * sumList[count + 1];
                    sumList[count + 1] = 1;
                } else {
                    sumList[count] += 3 * sumList[count + 1];
                    sumList[count + 1] = 1;
                }
            }

        }
        if (!stack.isEmpty()) {
            System.out.println(0);
            System.exit(0);
        }
        System.out.println(sumList[0]);
    }
}

배열을 이용하면 시간이 오래걸려 Queue나 Stack을 최대한 이용해 보려 했으나, 생각이 복잡해져 배열로 풀어보았다.

30개 이상의 괄호가 주어지지 않으니 30 Size의 배열을 만들어 놓고 1로 가득 채웠다.

괄호가 열릴때마다 count(차수)가 증가하며, 닫히면 count가 감소한다.

 

예시를 들어 설명하겠다.

예시 입력: (()[[]])([])

먼저 아래와 같은 배열이 준비될 것이다.

count = 0

1. '( ( ) [ [ ] ] ) ( [ ] )' 소괄호가 두번 열린다.
   count = 2
   
   
2.  '( ( ) [ [ ] ] ) ( [ ] )' 소괄호가 하나 닫히면서 count가 감소한다.
   count = 1
   

   

   ')' 괄호가 닫히면서 sumList[count]가 1이니 아래 코드에 따라 sumList[1] = sumList[2] * 2 가 실행될 것이다.
   

   else if (bracket == ')') {
       if (stack.isEmpty() || stack.pop() != 2) {
           System.out.println(0);
           System.exit(0);
       }
       count--;
       if (sumList[count] == 1) {
           sumList[count] = 2 * sumList[count + 1];
           sumList[count + 1] = 1;
       } else {
           sumList[count] += 2 * sumList[count + 1];
           sumList[count + 1] = 1;
       }
   }

    sumList[count + 1] = 1이 되는 이유는 아래서 설명하겠다. 배열은 다음과 같이 변한다.
   

   

3. '( ( ) [ [ ] ] ) ( [ ] )'   대괄호가 두개 열린다.
   count = 3
   
   
4. '( ( ) [ [ ] ] ) ( [ ] )'   대괄호가 하나 닫히며 count가 감소한다.
   count = 2
   ']' 대괄호가 닫히면서 sumList[count]가 1이니 아래 코드에 따라 sumList[2] = sumList[3] * 3 가 실행된다.
   

   else {
       if (stack.isEmpty() || stack.pop() != 3) {
           System.out.println(0);
           System.exit(0);
       }
       count--;
       if (sumList[count] == 1) {
           sumList[count] = 3 * sumList[count + 1];
           sumList[count + 1] = 1;
       } else {
           sumList[count] += 3 * sumList[count + 1];
           sumList[count + 1] = 1;
       }
   }

    여기서도 sumList[count + 1] = 1이 되나 아직 큰 역할은 없다. 배열은 아래와 같이 변해있다.
   

   

5. '( ( ) [ [ ] ] ) ( [ ] )'  또다시 대괄호가 하나 닫히며 count가 감소한다.
   count = 1
   이때는 아래와 같이 sumList[count]가 1이 아니다
   

   

   고로 sumList[count] += sumList[count+1] * 3 이라는 식이 작동될 것이다.
   

   

   sumList[1]의 값은 11이 된다.
   이제 'sumList[count + 1] = 1' 이 작동한다.
   만일 sumList[2]에 값이 초기화되지 않고 남아있다면 다음에 해당 배열을 사용할 수 없다.
   고로 계산이 끝난 위치의 값은 1이 되어야하고 마지막에는 결국 sumList[0]에 결과만이 남아있을 것이다.
   계산이 끝난 배열은 아래와 같다.
   

   

6. '( ( ) [ [ ] ] ) ( [ ] )' 소괄호가 하나 닫히면서 count가 감소한다.
   count = 0
   소괄호가 닫힐때의 조건문에 따라 sumList[0] = 2 * 11이 될 것이고,
   sumList[1] = 1로 초기화 될 것이다. 계산이 끝난 배열은 아래와 같다.
   

   

7. '( ( ) [ [ ] ] ) ( [ ] )' 소괄호 하나 대괄호 하나가 열리며 count 값이 2 증가한다.
   count = 2
   
   
8. '( ( ) [ [ ] ] ) ( [ ] )' 대괄호가 하나 닫히며 count 값이 1 감소한다.
   count = 1
   sumList[1] = 3 * 1 식이 작동하여 아래와 같은 배열이 된다.
   

   

9. '( ( ) [ [ ] ] ) ( [ ] )' 마지막으로 소괄호가 하나 닫히며 count 값이 1 감소한다.
   count = 0
   sumList[0] += 2 * 3, sumList[1] = 1 식이 작동하여 아래와 같은 배열이 된다.
   

   

10. 모든 괄호를 다 봤으므로 sumList[0] 즉 28이 잘 출력이 될 것이다.

풀때도 느낀것이고 다시 보면서도 느꼈지만 충분히 stack또는 queue를 이용해도 될 것 같다.
그렇게 느끼고 찾아보니 stack이든 queue든 사용하지 않고 분배법칙을 이용해서 풀었다.

종이에 한번이라도 써봤으면 달랐을까...
참고한 블로그는 아래와 같다.
[BOJ] 백준 2504번 괄호의 값 (Java) (tistory.com)

[BOJ] 백준 2504번 괄호의 값 (Java)

 

알고리즘은 결국 수학문제 풀기라는 것을 다시금 느꼈다.

많이 풀다보면 수학 실력도 늘게꺼니 생각해야겠다. ㅜ