압축

https://www.acmicpc.net/problem/1662

풀이

처음에는 문자열을 스택에 넣고 문자열을 합치면서 최종적으로 완성된 문자열을 길이를 리턴하는 방법을 풀었다.

하지만 문자열의 길이가 50인데 극단적인 케이스에서 문자열이 매우 길어 메모리초과를 겪을 수 있다.

따라서 스택에 스택에 들어가는 문자열의 길이만을 저장하면 되겠다는 생각이 들었다.

하지만 "(" 앞의 숫자는 반복해주는 회수이기 때문에 두 숫자를 구분할 필요가 있다. 그래서 Pair라는 클래스를 만들어 구현을 해야했다.

이후는 조건에 맞게 길이를 구해 스택에 넣어주면서 구할 수 있었다.

코드

import java.io.*;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] zip = br.readLine().split("");
        Stack<Pair> stack = new Stack<>();

        for (int i = 0; i < zip.length; i++) {
            String v = zip[i];
            if (zip[i].equals(")")) {
                int len = 0;
                while (stack.peek().key != -1) {
                    Pair p = stack.pop();
                    if (p.key == 1) {
                        len += Integer.parseInt(p.value);
                    }
                }
                stack.pop();
                Pair p = stack.pop();
                if(p.key == 0) {
                    len *= Integer.parseInt(p.value);
                }
                stack.push(new Pair(Integer.toString(len), 1));
            }
            else if (i < zip.length - 1 && zip[i + 1].equals("(")) {
                stack.push(new Pair(v, 0));
            }
            else if (zip[i].equals("(")) {
                stack.push(new Pair("(", -1));
            }
            else {
                stack.push(new Pair(Integer.toString(v.length()), 1));
            }
        }

        int ans = 0;
        while(!stack.isEmpty()) {
            Pair p = stack.pop();
            ans = ans + Integer.parseInt(p.value);
        }
        bw.write(ans+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Pair {
    String value;
    int key;

    public Pair(String value, int key) {
        this.value = value;
        this.key = key;
    }
}