https://www.acmicpc.net/problem/1662
입력 예시를 K(Q)라는 규칙에 따라서 쪼개본다면 다음과 같다. 3 3(56 2(7 1(9) ) )
쪼개진 문자열을 규칙에 맞춰서 변환하는 과정은 다음과 같다.
3 3(56 2(79) )
3 3(5679 79)
3 567979 567979 567979
반복되는 패턴을 보면서 저 패턴을 일반화 한다면 재귀적으로 문제를 해결 할 수 있겠다고 가닥을 잡았다.
재귀함수를 구현하는 키를 여는괄호와 닫는괄호로 정했다. 또한 반복의 대상이 되는 문자열을 추출하기 위해서 괄호의 여는 부분과 닫는 부분의 index가 필요했다.
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class Num1662 {
//압축
static char[] data;
static Map<Integer, Integer> openClose = new HashMap<>();
public static int rec(int start, int end){
int strLen = 0;
for (int i = start; i < end; i++) {
if (data[i] == '('){
int mul = data[i - 1] - '0';
strLen += mul * rec(i + 1, openClose.get(i)) - 1; //반복횟수(K)는 문자열의 수에서 제외해야해서 하나 빼준다
i = openClose.get(i);
}else {
strLen++;
}
}
return strLen;
}
public static void main(String[] args){
//3 3(56 2(7 1(9) ) )
Scanner sc = new Scanner(System.in);
Stack<Integer> stack = new Stack<>();
data = sc.nextLine().toCharArray(); // 입력받은 데이터를 문자 배열에 저장한다.
for (int i = 0; i < data.length; i++) {
if (data[i] == '(') stack.push(i); // 여는 괄호의 경우 INDEX를 스택에 저장한다.
else if (data[i] == ')') openClose.put(stack.pop(), i); // 닫는 괄호가 나오면, 여는 괄호의 INDEX를 KEY로 하고 닫는 괄호의 INDEX를 VALUE로 MAP에 저장한다.
}
int result = rec(0, data.length);
System.out.println(String.valueOf(result));
}
}
K(Q)패턴 앞에 문자열이 있기 때문에 패턴 밖의 문자열은 그대로 더해준다. 예제에서 예를 들자면 다음과 같이 빨간색으로 표시된 부분을 말한다.
3 3(56 2(7 1(9) ) )
패턴의 시작점인 여는 괄호를 만나는 순간 재귀는 깊어지면서 여는괄호의 index-1인 K와 리턴받은 문자열의 길이를 곱해주는데, 패턴의 K는 문자열로 취급하는 것이 아니기때문에 길이를 하나 빼줘야 한다.
또한 재귀로 값을 리턴받은 뒤에는 여는괄호와 쌍을 이루는 닫는괄호 다음부터 탐색을 시작할 수 있도록 현재 i의 값을 닫는괄호의 index로 변경해준다.
'Algorithm' 카테고리의 다른 글
A. 탐욕법 (Greedy) (0) | 2021.05.26 |
---|---|
[백준/BOJ 1074] Z (Java) (0) | 2021.05.10 |
[백준/BOJ 11729] 하노이 탑 이동 순서 (Java) (0) | 2021.05.03 |