728x90
반응형
https://www.acmicpc.net/problem/1662
풀이
- '(' 기호가 나올 때마다 대응하는 ')' 기호가 나올 때까지 함수를 호출하고 사이의 길이를 구한다
() 중간에 다른 괄호가 있는 경우 안쪽 괄호의 길이를 먼저 계산하여 리턴하면 바깥쪽 괄호의 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);
}
}
728x90
반응형
'백준 > Java' 카테고리의 다른 글
[백준][Java] 15650번 - N과 M (2) (0) | 2023.07.13 |
---|