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);
    }
}

스택

재귀

인데 큰 차이는 없다.

results matching ""

    No results matching ""