[백준 2504] 괄호의 값 - JAVA

문제 링크: https://www.acmicpc.net/problem/2504

접근 방법

1. 문제 핵심 규칙

• $() : 2점$
• $[] : 3점$
• $(X)$ : $2 * (X의 값)$
• $[X]$ : $3 * (X의 값)$
• $XY : X의 값 + Y의 값$

문제는 괄호의 쌍을 찾아 값을 더하거나 곱해 누적해야 하는 문제로 문제를 보자마자 Stack을 사용해야 한다는 것을 파악했습니다.

2. 코드의 핵심 전략

여기서 중요한 것은 괄호의 깊이에 따라서 곱하거나 더해줘야하는 로직이 존재하는데
저는 이것을 depth라는 더 깊은 깊이로부터의 괄호의 값은 곱해준 후 같은 깊이의 괄호인 경우 더해주는 로직을 구현했습니다.

• Stack (ArrayDeque): 현재 열린 괄호들을 저장하여 짝이 맞는지 확인합니다.

• Depth Array (depth[]): 각 중첩 레벨(n)에서 계산된 임시 점수를 저장합니다. 괄호가 닫힐 때 상위 레벨(n-1)로 값을 전달합니다.

3. 로직 상세 분석

① 괄호의 시작 '(' 또는 '['

괄호가 열리면 스택에 넣고 더 깊은 단계로 들어갑니다. 스택의 size가 곧 현재의 깊이가 됩니다.

② 괄호의 종료 ')' 또는 ']'

닫는 괄호가 나오면 두 가지를 체크합니다.

1. 유효성 검사: 스택이 비어있거나 짝이 맞지 않으면 errorFlag를 발생시키고 종료

2. 값 계산:

• 최하위 노드일 때: 안쪽에 아무런 값이 없다면(즉, depth[n] == 0), ()는 2점, []는 3점을 현재 깊이에 더하기
• 중첩된 노드일 때: 안쪽에 계산된 값(depth[n])이 있다면, 그 값에 2배 또는 3배를 곱하여 상위 단계(depth[n-1])로 전달하고 현재 단계는 초기화

후기

문제를 풀고 난 후 메모리 관리를 위해 이 문제의 스트링 길이를 파악했고
최대 30까지인 것을 파악한 후 스트링이 항상 옳게 제공되는 경우를 고려해
depth 배열의 길이를 16으로 설정했었습니다. (0 ~ 15까지의 depth를 저장하기 위함)

그러나 이 문제에서는 괄호가 옳지 않게 제공되는 경우가 존재했습니다.
만약 괄호가 (나 [로 29개가 들어오고 마지막에 )나 ]가 나오는 경우
depth의 길이가 16인 것에 비해 depth[29]의 접근을 요구해
ArrayIndexOutOfBoundsException이 발생할 수도 있었습니다.

이번 문제에서는 괄호의 모양이 틀린 경우에 대한 테스트케이스만 존재하고
해당 엣지 케이스가 존재하지 않아 통과했지만
앞으로는 엣지 케이스도 파악해서 신중하게 고려해야겠다는 생각을 하게 되었습니다.

코드

핵심 로직이 간단하기 떄문에 메서드를 구현하지 않고 메인 메서드에 작성했습니다.

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        ArrayDeque<Character> stack = new ArrayDeque<>();
        int[] depth = new int[16];

        boolean errorFlag = false;
        int n;
        char comp;
        for (char c : br.readLine().toCharArray()) {
            if (c == '(' || c == '[') {
                stack.push(c);
            }
            else {
                n = stack.size();
                if (n == 0) {
                    errorFlag = true;
                    break;
                }
                else {
                    comp = stack.pop();
                    if ((comp == '(' && c != ')') || (comp == '[' && c != ']')) {
                        errorFlag = true;
                        break;
                    }
                }

                if (depth[n] == 0) {
                    if (c == ')') depth[n-1] += 2;
                    else depth[n-1] += 3;
                }
                else {
                    if (c == ')') depth[n-1] += depth[n] * 2;
                    else depth[n-1] += depth[n] * 3;
                    depth[n] = 0;
                }

            }
        }

        System.out.println(errorFlag ? 0 : depth[0]);
    }
}