Java - [프로그래머스]60057 - 문자열 압축

출처

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

 

문제

 

설명이 길다. 하지만 읽다보면 간단하다.

만약 aaaabbbb를 1개 단위로 잘라(a, b) 압축하면, a와 b는 각각 네개이기 때문에 4a4b 이렇게 압축되고 , 2개 단위로 잘라서 (aa,bb) 압축하면 2aa2bb 이 되는데, 이렇게 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구하는 문제이다.

 

풀이

이 문제는 결국, 1개로 잘라 압축할지 부터 문자열의 길이만큼 잘라 압축할지 (이 경우 1"문자열" 이지만 1은 생략이므로 길이는 그대로이다) 모든 경우를 다 본 다음 정답을 구해야 하는 문제이다. 왜냐면 그 전에는 직접 어떤게 제일 좋은지 판단하기 어렵기 때문이다. 따라서 필자는 완전 탐색을 통해 문제를 해결하였다.

 

다음과 같은 단계를 거쳐 해결하면 된다.

 

먼저, 1개로 잘라 압축하는 것 부터 문자열의 길이만큼 압축하는 것을 모두 살펴보기 위해 큰 반복문을 하나 구성한다. 이후 문자열을 i개로 잘라 queue에 넣어주었다.

for (int i = 1; i <= s.length(); i++) {
    Queue<String> q = new LinkedList<>();
    int j = 0;
    while (j + i <= s.length() && i <= s.length() - 1) {
    	// i개(i 길이만큼)로 잘라 queue로 넣는다
        q.add(s.substring(j, j + i));
        j += i;
    }
    // 마지막 남은 문자열이 있는 경우, 그대로 queue에 넣어준다.
    if (!s.substring(j, s.length()).equals("")) {
        q.add(s.substring(j, s.length()));
    }
}

 

queue에 문자열을 모두 잘라 넣었으면, 본격적인 압축 작업을 시작한다. queue가 모두 빌 때 까지 작업을 반복하는데, 먼저 queue 맨 앞에있는 것을 뽑는다. 이후 현재 뽑은 것과 뒤에 동일한것이 있다면 2개 이상이라는 소리이므로, 같을 때 까지 모두 뽑아낸 다음 그 갯수를 세서 현재 뽑은 문자열 앞에 붙인다음 결과물 문자열 뒤에 붙인다.

 

 queue가 다 비면 모든 작업이 완료되었다는 소리 이므로, 압축작업이 진행된 결과 문자열의 길이를 answer 리스트에 넣는다.

String x = "";
while (!q.isEmpty()) {
    String now = q.poll();
    int n = 1;
    while (!q.isEmpty() && q.peek().equals(now)) {
        q.poll();
        n++;
    }

    x = n!=1 ? x + n + now : x + now;

}
answer.add(x.length());

 

이렇게 모두 반복이 끝나면, answer 리스트에 있는 값중 가장 짧은 값을 return한다.

 

전체 코드

import java.util.*;
class Solution {
    public int solution(String s) {
        List<Integer> answer = new ArrayList<>();
        for (int i = 1; i <= s.length(); i++) {
            Queue<String> q = new LinkedList<>();
            int j = 0;
            while (j + i <= s.length() && i <= s.length() - 1) {
                q.add(s.substring(j, j + i));
                j += i;
            }
            if (!s.substring(j, s.length()).equals("")) {
                q.add(s.substring(j, s.length()));
            }
            String x = "";
            while (!q.isEmpty()) {
                String now = q.poll();
                int n = 1;
                while (!q.isEmpty() && q.peek().equals(now)) {
                    q.poll();
                    n++;
                }
                
                x = n!=1 ? x + n + now : x + now;
                
            }
            answer.add(x.length());
        }
        return Collections.min(answer);
    }
}