[백준][JAVA] 1662번 - 압축

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

---

풀이

1. '(' 기호가 나올 때마다 대응하는 ')' 기호가 나올 때까지 함수를 호출하고 사이의 길이를 구한다
   () 중간에 다른 괄호가 있는 경우 안쪽 괄호의 길이를 먼저 계산하여 리턴하면 바깥쪽 괄호의 Q 길이를 구할 수 있다

 

압축 부분 K(Q)의 Q의 길이를 구하는 것이 관건인 문제인 것 같다. 문제를 처음 봤을 때 stack를 생각했고 (, )를 사이 문자의 개수를 세어 Q의 길이를 계산하는 방식의 풀이 방법을 생각했으나 K(K(Q))와 같은 형태에서 바깥쪽 K(Q)의 Q의 길이를 구하는 데에 어려움이 있었다. 조금 더 생각해 보니 재귀함수를 호출해서 Q의 길이를 구하는 방법으로 문제를 해결할 수 있었다.

---

답

import java.io.*;
import java.util.StringTokenizer;
import java.lang.*;

class Main {
	
	public static int unzip(String S, int i) {
		int len = 0;
		int multi = S.charAt(i - 2) - '0';
		int count;
		while (i < S.length()) {
			if (S.charAt(i) == '(') {
				i++;
				len += unzip(S, i) - 1;
				count = 1;
				while (count > 0) {
					if (S.charAt(i) == '(')
						count++;
					else if (S.charAt(i) == ')')
						count--;
					i++;
				}
			}
			else if (S.charAt(i) == ')') {
				i++;
				break;
			}
			else {
				len++;
				i++;
			}
		}
		return len * multi;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String S = br.readLine();
		int i = 0;
		int totalLen = 0;
		int count;
		while (i < S.length()) {
			if (S.charAt(i) == '(') {
				i++;
				totalLen += unzip(S, i) - 1;
				count = 1;
				while (count > 0) {
					if (S.charAt(i) == '(')
						count++;
					else if (S.charAt(i) == ')')
						count--;
					i++;
				}
			}
			else {
				totalLen++;
				i++;
			}
		}
		System.out.print(totalLen);
	}
}