[BOJ] 1662번 압축 Java 풀이

https://www.acmicpc.net/problem/1662

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

public class Main {
  static int[] paren = new int[50];
  static char[] s;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Stack<Integer> st = new Stack();
    s = br.readLine().toCharArray();

    for (int i = 0; i < s.length; i++) {
      if (s[i] == '(') st.push(i);
      if (s[i] == ')') paren[st.pop()] = i;
    }
    System.out.println(traversal(0, s.length));
  }

  static int traversal(int start, int end) {
    int sLength = 0;

    for (int i = start; i < end; i++) {
      if (s[i] == '(') {
        sLength += (s[i - 1] - '0') * traversal(i + 1, paren[i]) - 1;
        i = paren[i];
      } else {
        sLength++;
      }
    }
    return sLength;
  }
}

• 스택을 처음 배울 때 연습문제로 풀어보는 parentheses 같이 괄호가 잘 닫혀있는 문자열인지 아닌지를 판별하는 문제와 비슷하다.
• 대신 앞 괄호마다 뒷괄호가 닫히는 인덱스를 저장하는 배열을 하나 만들어서 그 지점에 도달하면 그 전 숫자와 그동안 읽어온 문자열길이를 곱해주고, 괄호 길이 1을 빼주는 식으로 recursion 로직을 짜면 쉽게 풀 수 있는 문제이다