(2020카카오) 문자열 압축 Java

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

문제를 이해하는데 시간이 걸렸다.

 

n개씩 자르면서, 각 시행에 대하여 길이를 구한다음 최소값을 구하는것이 문제의 목표이다.

(단, 맨 앞에서부터 n개씩 잘라야된다. 어디서부터 n개씩 자를지 경우의 수를 구할 필요가 없다.)

입출력 예

	s	result
1	"aabbaccc"	7
2	"ababcdcdababcdcd"	9
3	"abcabcdede"	8
4	"abcabcabcabcdededededede"	14
5	"xababcdcdababcdcd"	17

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

 

필자의코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;

        Queue<String> compareQueue = new LinkedList<>();
        PriorityQueue<String> list = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() >= o2.length() ? 1 : -1;
            }
        }
        );

        for (int n = 1; n <= s.length(); n++) {
            String cut;
            for (int i = 0; i <= s.length();) {
                if(i+n<s.length()) {
                    cut = s.substring(i, i + n);
                }else{
                    cut = s.substring(i);
                }
                compareQueue.offer(cut);//큐에 집어넣기
                i += n;//n칸씩 증가연산
            }

            String result = "";
            while (!compareQueue.isEmpty()) {
                String r = compareQueue.poll();
                int i = 1;
                while (r.equals(compareQueue.peek())) {
                    compareQueue.poll();//peek한거 빼버리기
                    i++;//개수추가
                }
                if (i != 1) {//1이아닌경우 3abab
                    result += (i + r);
                } else {//1인경우 abab
                    result += r;
                }
            }
            //결과값 큐에 넣어놓기
            list.offer(result);
        }

        answer = list.poll().length();
        return answer;
    }
}

주석을 참고하면 이해가 가능하다.

 

 

다른 효율성 좋은 코드

class Solution {
    public int solution(String s) {
        int min = s.length();
        int len = s.length()/2+1;
        for(int i = 1; i < len; i++) {
            String before = "";
            int sum = 0;
            int cnt = 1;
            for(int j = 0; j < s.length();) {               
                int start = j;
                j = (j+i > s.length()) ? s.length():j+i;
                String temp = s.substring(start, j);
                if(temp.equals(before)) {
                    cnt++;
                } else {
                    if(cnt != 1) {
                        sum += (int)Math.log10(cnt)+1;
                    }
                    cnt = 1;
                    sum+=before.length();
                    before = temp;
                }
            }
            sum+=before.length();
            if(cnt != 1) {
                sum += (int)Math.log10(cnt)+1;
            }
            min = (min > sum) ? sum : min;
        }

        return min;
    }
}

for문 안의 j~부분은 필자의 코드와 마찬가지로 자르는 부분에 해당한다.

if문으로 이전 before와 같은지 확인하고, 같으면 count값을 올려준다.

log10 값을 이용해서 자리수(10의 몇승인지)를 계산한다.