[백준1662] 압축 / Java

링크 | https://www.acmicpc.net/problem/1662

문제 |

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력 |

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력 |

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

예제 |

Solution |

• 33(562(71(9)))
  71(9)=79 -> 2
  2(79)=7979 -> 4, 562(79)=567979 -> 6
  3(567979) -> 18
  그러므로 33(562(71(9))) -> 19
• 스택을 이용하여 괄호 내의 숫자를 카운트하고 여는괄호 바로 앞 숫자와 곱하는 재귀함수를 구현하였다.
• 닫는 괄호의 idx는 static을 이용하여 전역변수로 설정.

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

public class Compression {
	static String[] splitStr;
	static int idx;
	static Stack<String> stack = new Stack<String>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();		
		splitStr = str.split("");

		System.out.println(StrLength(0));
	}
	
	static int StrLength(int start) {
		int len = 0;
		for (int i=start; i<splitStr.length; i++){
			if (splitStr[i].equals("(")) {
				stack.push(splitStr[i]);
				len += Integer.parseInt(splitStr[i-1])*StrLength(i+1)-1;
				i = idx;;
	
			}else if(splitStr[i].equals(")")){
				if (!stack.empty() && stack.peek().equals("(")) {
					idx = i;
					stack.pop();
					return len;
				}
			}else {
				len++;
			}
		}
		return len;		
	}
}