스택

백준 2504번 괄호의 값을 자바를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/2504

분배법칙

문제의 시작점까지는 도달했는데 그 이후로 진행이 되질 않았다. 전체값을 할당해줄 result 와 중간 계산을 위한 tmp를 따로 두고 계산을 진행해야 한다는 것까지는 감을 잡았지만 그 이후에 어찌 해야할지를 파악하지 못해 결국 다른 사람들의 풀이를 참고했다. 꽤 길게 고민하던 중 결국 다른 사람의 풀이를 보았을 때 분배법칙이란 단어를 보니 직관적으로 와닿았다.
혼자 고민할 때는 (X) 에서 X의 값을 모두 계산하고 )로 닫힐 때 *2 를 해줄 생각을 했다. 하지만 분배법칙이란 키워드로 생각해본다면 X의 온전한 값을 다 계산하고 나서 2를 곱할 것이 아니라 계산해줄 녀석을 만나면 바로 계산하면 되는 것이다. 예를 들면 다음과 같다.

([()]) 가 있을 때 가장 바깥의 (...) 안에 있는 [()] 를 온전히 다 계산하여 6*2 를 할 것이 아니다. 가장 첫 (를 만날 때 2, 다음 [를 만날 때 *3을 하고 그 다음 (를 만날 때 *2를 해서 12를 만드는 것이다. 이렇게 tmp의 값을 만들어주고 닫는 괄호를 만날 때 전체 result 값에 더해주면 되는 것이다. 지금 든 예시의 경우 닫는 괄호가 3개이기 때문에 모든 닫는 괄호마다 result에 tmp 값을 더할 수는 없다. 스택의 peek가 아닌, 입력받은 문자열 기준으로 봤을 때 쌍을 이루며 닫히는 괄호에서만 tmp 값을 더해주면 된다. 이 예시의 경우에서는 가장 처음 닫히는 괄호인 )에서 result += tmp 가 이루어지는 것이다.
바로 이 지점을 파악하지 못해서 닫힐 때마다 tmp 값을 더하게 짜놔서 한참 헤맸다.

올바르지 않을 경우

닫는 괄호마다 알맞은 pair 를 이루는지 확인해주고, 그렇지 않으면 result 값을 0으로 만들면 된다. 가장 마지막에 출력해주기 전에 한 번 더 stack 이 비어있으면 정상이고 그렇지 않으면 0을 출력하면 된다.

아래는 내가 제출한 전체 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class boj2504 {

    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        String input = bfr.readLine();

        Stack<Character> stk = new Stack<>();
        int result = 0;
        int tmp = 1;

        L1: for(int i=0; i<input.length(); i++){
            char c = input.charAt(i);

            switch(c){
                case '(':
                    stk.add('(');
                    tmp *= 2;
                    break;

                case '[':
                    stk.add('[');
                    tmp *= 3;
                    break;

                case ')':
                    if(stk.isEmpty() || stk.peek()!='('){
                        result = 0;
                        break L1;
                    }
                    else{
                        if(input.charAt(i-1)=='(')  result += tmp;
                        stk.pop();
                        tmp /= 2;
                    }
                    break;

                case ']':
                    if(stk.isEmpty() || stk.peek()!='['){
                        result = 0;
                        break L1;
                    }
                    else{
                        if(input.charAt(i-1)=='[')  result += tmp;
                        stk.pop();
                        tmp /= 3;
                    }
                    break;
            }
        }

        if(!stk.isEmpty()) System.out.println(0);
        else System.out.println(result);
    }
}

마치며

첫 눈에는 간단해 보여서 덤볐는데 막상 안 풀리니까 좀 조급해졌다. 매번 느끼는 거지만 문제 그대로 보기보다는 이 문제를 해결하기 위한 가장 간단한 그림이 무엇일까를 차분히 고민할 수 있는 여유가 있어야 하는 것 같다. 그 여유는 많은 시간과 연속된 도전으로부터 올텐데... 공부량이 그에 미치지 못하니 여유가 없는 것 같다. 지금보다 조금씩만 더.. 꾸준해지자.