[백준/boj] 1662: 압축 (Java) / 재귀 / 스택

문제

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

1662번: 압축

풀이

import java.io.*;
import java.util.*;

public class Main {
	static int[] rightIdxs = new int[51];
	static String[] input;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<>();
		input = br.readLine().split("");
		
		for(int i=0; i< input.length; i++) {
			String value = input[i];
			if(value.equals("(")) stack.add(i); // ( 의 위치
			if(value.equals(")")) rightIdxs[stack.pop()] = i; // rightIdxs 배열 [짝궁 '(' 괄호]번째에 ')'의 위치를 할당한다. 
		}
		
		System.out.println(getLength(0, input.length));
	}
	
	private static int getLength(int start, int end) {
		int len = 0;
		for(int i=start; i< end; i++) {
			if(input[i].equals("(")) {
				len += Integer.parseInt(input[i-1]) * getLength(i+1, rightIdxs[i]) -1 ; // -1은 '(' 앞에 있는 문자 길이(1)를 빼는 것!
				i = rightIdxs[i];
			} else {
				len++;
			}
		}
		return len;
	}
}

 

1. '(' 짝궁 ')'의 위치를 저장하는 배열 채우기

먼저, '(' 의 짝궁 ')'를 찾기 위해서는 stack을 사용한다! (선입 후출) 

'(' 일때는 스택에 해당 괄호의 위치(i)를 삽입!
')' 일때는 pop()했을 때 나온 int값이 자신의 짝궁 '('의 위치이다!

압축 문제는 '(' 부터 자신의 짝궁 ')' 의 위치까지의 문자열 길이를 구해서 '(' 앞의 숫자를 곱해야한다!

때문에, '(' 의 짝궁 ')'의 위치를 저장하는 배열 rightIdxs를 만들었다.

rightIdxs['('의 위치] = 자신의 짝궁 ')'의 위치;

 

2. 함수(재귀)를 통해 압축해제한 문자열의 길이 구하기 ! 

start 위치부터 end 바로전 위치까지 살펴보면서

2-1. '(' 가 아니면 숫자이므로 len++; 

2-2. '(' 이면 현재까지 누적해온 len에 '(' 앞 숫자 에 '(' 다음 위치부터 짝궁 ')' 위치 전까지의 문자열 길이(재귀)를 곱한 값을 더한다.

이때, 1을 빼는 이유는 2-1. 과정에서 len++된 '( 앞 숫자' 의 길이(1)를 빼주어야하기 때문이다.

(재귀) 설명

• '(' 다음 위치 는 start가 되고 짝궁 ')'의 위치는 end가 된다.
• 2-1, 2-2 과정을 거쳐 len이 반환된다.