[BOJ] 1662 - 압축 JAVA

www.acmicpc.net/problem/1662

1662번: 압축

문제

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

입력

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

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다.

예제 입력 1

33(562(71(9)))

예제 출력 1

19

 

 

 

 

 

 

 

 

 

풀이 1. (틀린 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Stack<Character> stk = new Stack<>();
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == ')') break;
            stk.push(str.charAt(i));
        }

        int length = 0;
        while(!stk.isEmpty()) {
            if(stk.peek() == '(') {
                stk.pop();  // 괄호 제거
                length = length * (stk.pop() - '0');  // 압축 해제
            }else {
                length += 1;
                stk.pop();
            }
        }
        System.out.println(length);
    }
}

 

예제의 경우에서만 생각하고 코드를 짜서 틀렸다.

 

이 코드는 하나의 괄호 안에 여러 괄호가 포함되는 경우를 처리하지 못한다.

 

 

 

 

 

풀이 2. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");
        Stack<String> stk = new Stack<>();  // 문자열의 길이도 스택에 함께 넣는다. 길이는 한자리를 넘어갈 수 있으므로 반드시 String 사용

        for(int i = 0; i < arr.length; i++) {
            if(!arr[i].equals(")")) {
                stk.push(arr[i]);  // ")" 등장할때마다 로직 수행. ")"전까지는 전부 스택에 담는다
            }else {
                int cnt = 0;
                while(!stk.peek().equals("(")) {  // 괄호를 풀기 위해 "(" 나올 때까지 pop 한다
                    String output = stk.pop();
                    if(output.equals("*")) {
                        int len = Integer.parseInt(stk.pop());
                        cnt += len;
                    }else {
                        cnt += 1;
                    }
                }
                stk.pop();  // "(" 제거
                int len = Integer.parseInt(stk.pop());
                cnt *= len;  // 압축 해제
                stk.push(String.valueOf(cnt));
                stk.push("*");  // "*" 밑에 있는 숫자는 문자열이 아니라 숫자의 길이를 나타냄
            }
        }

        int ans = 0;
        while(!stk.isEmpty()) {
            if(stk.peek().equals("*")) {
                stk.pop();
                ans += Integer.parseInt(stk.pop());
            }else {
                stk.pop();
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

 

같은 레벨에 있는 여러 괄호를 정상적으로 처리하려면?

 

(처음에 생각한 로직)

1. 일단 ")"이 등장할 때마다 처리 로직을 수행해야 하는 부분은 명확하다고 봤다. ")"이 나오기 전까지 스택에 담고 ")"이 나오면 오직 수행

2. 그 후 "("이 나오기 전까지 문자들을 빼면서 개수(길이)를 센다.

3. "("이 나오면 제거하고 그 다음에 나오는 숫자를 빼서 지금까지 센 길이에 곱한다. (= 압축 해제)

4. 압축이 해제된 길이 만큼의 아무 문자나 스택에 넣는다.(중요한 건 길이이기 때문에 어떤 문자를 넣든 중요하지 않다)

 

4번 단계에서 압축 해제한 문자를 다시 넣는 것이 조금은 낭비라고 느껴졌다.

하지만, 최초 입력 문자열의 길이는 최대 50인데, 가장 압축을 많이 하는 경우인 "9( )" 사이에 47개의 숫자를 넣는 경우를 생각하면 47 * 9 = 463 으로 그다지 크지 않다.

 

N 제한이 작아서 무리가 없는 수준이지만 그래도 이를 줄일 수 있는 더 좋은 방법이 있었다.

스택에 기존 문자열과 압축 해제한 문자열의 길이를 함께 저장하는 것이다.

 

들어가는 숫자가 문자열이 아니라 문자열의 길이임을 표시하기 위해 "*"를 함께 넣어서 구분한다.

 

 

 

자료구조 문제에서 기초적인 구현력을 요구하는 경우가 많은 것 같다.

 

나중에 자료구조만 따로 모아서 풀어봐야겠다.