[Java] 백준 1662번 - 압축

 

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

1662번: 압축

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

 

 

접근 방법

 

[처음 코드]

입력 문자열을 stack 에 push 한 뒤, 단순하게 문자열 끝(stack의 top)부터 탐색을 진행했다. 탐색을 진행할 때는 세가지 케이스를 나눴다. 먼저 그냥 숫자이면 len을 하나씩 증가시키고, ')'이면 pop 하고, '('이면 '('의 앞 숫자(k)를 len에 곱했다. 

 

그러나 아래 코드는 문제에서 주어진 예제는 맞췄으나, 또 다른 반례를 생각하지 못했다. 

반레 : () 안에 압축 문자열이 여러개가 포함이 될 때  -> ex. 45(12)53(52(1111)42(222)) 

import java.util.*;
public class Main {

    public static void main(String[] args) {

        String input;
        Scanner sc = new Scanner(System.in);
        input = sc.next();
        int inputLen = input.length();

        char[] arr = input.toCharArray();

        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < inputLen; i++){
            stack.push(arr[i]);
        }

        int len = 0;
        while(!stack.empty()){
            char topChar = stack.peek();
            if(topChar == ')') {
                stack.pop();
            }
            else if(topChar == '('){
                stack.pop();
                int k = (int)stack.pop() - '0';
                len = len*k;
              
            }
            else{
                len++;
                stack.pop();
            }
        }
        System.out.println(len);
    }
}

 

[정답 코드]

입력 문자열을 끝이 아닌 처음부터 stack에 push 해가면서 탐색을 진행한다. 단 ')'를 만나기 전까지 탐색을 진행한다. ')'를 만나면 push 했던 문자열들을 pop 해가면서 압축 문자열을 해제하는 로직을 수행한다. 이 때 while문을 돌면서 '('를 만나기 전까지 stack에서 pop해가면서 길이를 계산한다. K(Q)의 길이를 알아냈다면, 그 길이를 다시 stack에 push하는데, 이는 하나의 괄호 쌍 안에 여러개의 압축 문자열이 있을 때를 위한 것이며, 계산한 압축 문자열의 길이와 기존에 입력 문자열을 구분하기 위해 계산한 압축 문자열의 길이를 push 할 때에는 길이를 push한 뒤에 바로 "+"를 push 해준다. 

 

입력 문자열의 끝까지 push하면서 탐색을 끝냈다면, stack에서 하나씩 Pop 해가면서 최종 길이를 계산한다.

  

 

*주의 :  Stack Type을 Char형으로 정의 시 형변환 하는 과정에서 오류 -> String Type으로 정의해야한다.

import java.util.*;
import java.io.*;
public class BOJ1662_압축 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");

        Stack<String> stack = new Stack<String>();
        for(int i = 0; i < arr.length; i++){

            if(!arr[i].equals(")")) {stack.push(arr[i]);}
            else {
                int cnt = 0;
                while (!stack.peek().equals("(")) {
                    String topStr = stack.pop();
                    if (topStr.equals("+")) {
                        int len = Integer.parseInt(stack.pop());
                        cnt += len;
                    } else cnt++;
                }
                stack.pop(); // ( 제거
                int k = Integer.parseInt(stack.pop());
                cnt = cnt * k;
                stack.push(String.valueOf(cnt));
                stack.push("+");
            }
     }
        int answer = 0;
        while(!stack.empty()){
            if(stack.peek().equals("+")){
                stack.pop();
                //System.out.println(stack.peek());
                answer += Integer.parseInt(stack.pop());
            }
            else{
                stack.pop();
                answer++;
            }
        }
        System.out.println(answer);
    }
}

 

 

 

참고 : https://codeung.tistory.com/256