[백준/BOJ 1662] 압축 (Java)

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

입력 예시를 K(Q)라는 규칙에 따라서 쪼개본다면 다음과 같다.  3 3(56 2(7 1(9) ) )

쪼개진 문자열을 규칙에 맞춰서 변환하는 과정은 다음과 같다.

3 3(56 2(79) )

3 3(5679 79)

3 567979 567979 567979

반복되는 패턴을 보면서 저 패턴을 일반화 한다면 재귀적으로 문제를 해결 할 수 있겠다고 가닥을 잡았다. 

재귀함수를 구현하는 키를 여는괄호와 닫는괄호로 정했다. 또한 반복의 대상이 되는 문자열을 추출하기 위해서 괄호의 여는 부분과 닫는 부분의 index가 필요했다. 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Num1662 {
  //압축
  static char[] data;
  static Map<Integer, Integer> openClose = new HashMap<>();

  public static int rec(int start, int end){
    int strLen = 0;
    for (int i = start; i < end; i++) {
      if (data[i] == '('){
        int mul = data[i - 1] - '0';
        strLen += mul * rec(i + 1, openClose.get(i)) - 1; //반복횟수(K)는 문자열의 수에서 제외해야해서 하나 빼준다
        i = openClose.get(i);
      }else {
        strLen++;
      }
    }
    return strLen;
  }

  public static void main(String[] args){
    //3 3(56 2(7 1(9) ) )
    Scanner sc = new Scanner(System.in);
    Stack<Integer> stack = new Stack<>();
    data = sc.nextLine().toCharArray(); // 입력받은 데이터를 문자 배열에 저장한다.
    for (int i = 0; i < data.length; i++) {
      if (data[i] == '(') stack.push(i); // 여는 괄호의 경우 INDEX를 스택에 저장한다.
      else if (data[i] == ')') openClose.put(stack.pop(), i); // 닫는 괄호가 나오면, 여는 괄호의 INDEX를 KEY로 하고 닫는 괄호의 INDEX를 VALUE로 MAP에 저장한다.
    }
    int result = rec(0, data.length);
    System.out.println(String.valueOf(result));
  }
}

K(Q)패턴 앞에 문자열이 있기 때문에 패턴 밖의 문자열은 그대로 더해준다. 예제에서 예를 들자면 다음과 같이 빨간색으로 표시된 부분을 말한다. 

3 3(56 2(7 1(9) ) )

패턴의 시작점인 여는 괄호를 만나는 순간 재귀는 깊어지면서 여는괄호의 index-1인 K와 리턴받은 문자열의 길이를 곱해주는데, 패턴의 K는 문자열로 취급하는 것이 아니기때문에 길이를 하나 빼줘야 한다.

또한 재귀로 값을 리턴받은 뒤에는 여는괄호와 쌍을 이루는 닫는괄호 다음부터 탐색을 시작할 수 있도록 현재 i의 값을 닫는괄호의 index로 변경해준다.