[백준 1662, Java] 압축

11월 22일 내내 이거 풀었는데, 또 풀고나니 왜그렇게 오래걸렸나 싶다. 

 

문제

www.acmicpc.net/problem/1662

1662번: 압축

풀이

• - 우선 주어진 문자열의 구성을 봐야한다. 1개 문자열/ 괄호/Q(괄호안의 문자) /K 이렇게 있다. 한 스택에 push를 할때는 구분을 해줘야 한다. 이걸 생각하기 까지 꽤 오래걸렸다.

• - 33(562(71(9)))가 있을 때 1(9)를 계산(1*9) 한 후 결과를 다시 stack 에 push를 한다. 이때 스택에 남아있는 숫자와 구분하기 위해 *를 같이 push를 하는데, 이는 * 앞의 수는 문자열1개아 아닌 길이임을 구분하기 위해서이다. 

• - 문자열을 순회하면서 )가 아니면 stack에 push 한다

• - )가 나오면 괄호안 문자열의 길이를 구하기 위해 (가 나올때 까지 stack에서 pop을 한다. pop을 할때 count 를 1 증가시키는데, *가 나오면 *뒤에 있는 숫자만큼 count에 더해준다. 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static String[] compressed;
    public static Stack<String> stack;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        compressed = br.readLine().split("");
        stack = new Stack<>();
        calculateDecompressedLength();

        long result = getLength();
        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();

    }
    public static void calculateDecompressedLength(){
        for(int index = 0; index<compressed.length; index++){
            String currentChar = compressed[index];

            if(!currentChar.equals(")")){
                stack.push(currentChar);
            }
            else{
                int count = 0;

                while(!stack.peek().equals("(")){
                    String popedChar = stack.pop();

                    //* 앞에 있는 수는 문자열일 아니라 길이
                    if (popedChar.equals("*")) {
                        count += Integer.parseInt(stack.pop());
                    } else {
                        ++count;
                    }
                }
                // 스택에서 ( 제거
                stack.pop();

                //압축문자 해제 K(Q) K* Q의 길이(count)
                int k = Integer.parseInt(stack.pop());
                count *=k;

                stack.push(String.valueOf(count));
                stack.push("*");
            }
        }
    }
    public static long getLength(){
        long length = 0;
        while(!stack.isEmpty()){
            String popedString = stack.pop();

            if(popedString.equals("*")){
                length += Integer.parseInt(stack.pop());
            }
            else{
                length += 1;
            }
        }

        return length;
    }
}

 

틀린풀이1

- 문자열을 더해주는 경우 : 메모리 초과

    public static int getDecompressedLength(){
        Stack<String>  stack = new Stack<>();
        for(int index = 0 ; index<compressed.length; index++){
            String currentString = compressed[index];
            if(!currentString.equals(")")){
                stack.push(currentString);
            }
            else{
                StringBuilder characterArray = new StringBuilder();
                while(!stack.peek().equals("(")){
                    characterArray.insert(0, stack.pop());
                }
                stack.pop(); // "(" pop하기

                int K = Integer.parseInt(stack.pop());
                StringBuilder repeatedCharacterArray = new StringBuilder();
                for(int count = 1; count<=K; count++){
                    repeatedCharacterArray.insert(0, characterArray);
                }
                stack.push(new String(repeatedCharacterArray));
            }
        }

        StringBuilder decompressed = new StringBuilder();
        while(!stack.isEmpty()){
            decompressed.insert(0, stack.pop());
        }

        return decompressed.length();
    }

 

틀린풀이 2

- 괄호 안에 괄호를 구분하지 못한 경우 

-반례 : 3(3(3(2(2)2(2))))

    public static void getDecompressedLength(){
        Stack<Character>  stack = new Stack<>();
        for(int index = 0 ; index<compressed.length(); index++){
            char currentString = compressed.charAt(index);
            if(currentString!=')'){
                stack.push(currentString);
            }
            else{
                while(stack.peek()!='('){
                    stack.pop();
                    ++ length;
                }
                stack.pop(); // "(" pop하기

                int K = Character.getNumericValue(stack.pop());
                length = length * K;

            }
        }

        length += stack.size();

    }

 

틀린풀이 3

- 괄호덩어리를 구분하지 못한경우

-45(12)53(52(1111)42(222))

    public static void getDecompressedLength(){
        Stack<Character>  stack = new Stack<>();
        Stack<Long> lengthStack = new Stack<>();
        long subLength = 0;
        for(int index = 0 ; index<compressed.length(); index++){
            char currentString = compressed.charAt(index);
            if(currentString!=')'){
                stack.push(currentString);
            }
            else{
                while(stack.peek()!='('){
                    stack.pop();
                    ++ subLength;
                }
                stack.pop(); // "(" pop하기

                int K = Character.getNumericValue(stack.pop());
                subLength = subLength * K;
                lengthStack.push(subLength);


                if(index == compressed.length()-1){
                    break;
                }
                else if(compressed.charAt(index+1)!=')'){
                    subLength = 0;
                }
                else{
                    int temp = 0;
                    while(!lengthStack.isEmpty()) {
                        temp +=lengthStack.pop();
                    }
                    subLength = temp;
                }
            }
        }
        if(!lengthStack.isEmpty()){
            length = lengthStack.pop();
        }
        length += stack.size();

 

 

반례

45(12)56(52(1111111111)45(2532141))

45(12)56(52(1111111111)45(2532141))11111