제출 코드
- 사용 알고리즘 :
재귀
압축문자열의 길이를 반환하는 메서드를 만들고, 압축된 부분을 만나면 압축된 내부 문자열을 다시 재귀로 길이를 구하도록 하도록 풀었다.
압축된 부분이 어디까지인지 하나씩 세어가는 부분이 재귀호출하면서도 중복해서 탐색하게 되지만, 문자열 길이가 최대 50인 점을 생각하면 시간초과 나진 않을것이라 생각하고 풀었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class G1662_compression {
static int decompress(String s) { // 압축을 풀었을 때 길이를 반환
int len = s.length();
int cnt = 0;
for(int i=0; i<len; i++) {
if(s.charAt(i)=='(') { // 내부의 압축문자열 발견
int start = i+1;
int cnt_left = 1; // '('의 개수
int cnt_right = 0; // ')'의 개수
while(cnt_left != cnt_right) { // 압축된 부분이 어디까지인지 인덱스 찾기 (가장 외부 괄호 기준)
if(s.charAt(++i)=='(') cnt_left++;
else if(s.charAt(i)==')') cnt_right++;
}
int K = s.charAt(start-2)-'0';
cnt += K * decompress(s.substring(start, i)) - 1; // 앞전에 cnt올려줬던거 하나 빼주기
}else {
cnt++;
}
}
return cnt;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(decompress(br.readLine()));
}
}