algo
알고리즘 스터디 참여의 계기가 된 이번 코테에서와 비슷한 문제라고 성지곰이 말해줬는데, 꽤 비슷했다. 문제를 못 푼 한을 여기서 풀게 되었다.
재귀를 쓴 방식으로 해결을 했는데, 나중에 GPT한테 보여줬는데, 더 깔끔하게 개선해줬고, 스택으로도 푸는 방법을 알려줬다.
https://www.acmicpc.net/problem/1662
//재귀 버전
import java.io.*;
import java.util.*;
public class Main {
static int[] pair;
static String orig;
public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
orig = br.readLine();
pair = new int[orig.length()];
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0; i < orig.length(); i++) {
char c = orig.charAt(i);
if(c == '(') {
stack.push(i);
} else if(c == ')') {
pair[stack.pop()] = i;
}
}
System.out.println(doSome(0, orig.length()));
}
public static int doSome(int s, int e) {
int length = 0;
for(int i = s; i < e; i++) {
if(orig.charAt(i) == '(') {
int k = orig.charAt(i - 1) - '0';
length--;
length += k * doSome(i + 1, pair[i]);
i = pair[i];
} else {
length++;
}
}
return length;
}
}
//스택 버전 Gemini
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
// 괄호 들어가기 전의 길이를 저장하는 스택
Stack<Integer> lenStack = new Stack<>();
// 곱해줄 수(K)를 저장하는 스택
Stack<Integer> mulStack = new Stack<>();
int currentLength = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
// 1. '(' 바로 앞의 숫자는 문자가 아니라 곱셈 계수(K)임
// 따라서 현재 길이 카운트에서 1을 빼야 함
currentLength -= 1;
int k = s.charAt(i - 1) - '0';
// 2. 현재 상태(지금까지의 길이, 곱할 숫자) 백업(Push)
lenStack.push(currentLength);
mulStack.push(k);
// 3. 괄호 안의 길이를 새로 세기 위해 초기화
currentLength = 0;
} else if (c == ')') {
// 1. 저장해둔 정보 복구(Pop)
int k = mulStack.pop();
int prevLength = lenStack.pop();
// 2. 계산: 이전 길이 + (현재 괄호 안 길이 * K)
currentLength = prevLength + (currentLength * k);
} else {
// 숫자: 길이 1 증가
currentLength++;
}
}
System.out.println(currentLength);
}
}
스택
재귀
인데 큰 차이는 없다.