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

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

입출력 예에 대한 설명

입출력 예 #1

입출력 예 #2

입출력 예 #3

입출력 예 #4

입출력 예 #5

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의 몇승인지)를 계산한다.