2020 카카오 코딩 테스트 문자열 압축 java

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

 

나의 풀이

 

 내가 이해한 이 문제의 핵심 요지는 축의 기준이 되는 문자열을 유닛(코드상 unit)이라 할때 이 유닛의 길이는 일정해야 한다는 것. 다시 말하자면 주어진 문자열 s에서 어떤 부분은 unit의 길이가 1이고 어떤 부분은 unit의 길이가 1이 아닌 n인 경우가 존재할 수 없다는 말이다. 예를 들자면 aabbcccabab를 2a2b3c2ab로는 압축할 수 없다. aabbccc 부분은 unit의 길이가 1인데, abab부분은 unit이 ab이므로 길이가 2가 되기 때문이다.

 때문에 unit의 길이를 몇으로 했을 때 최소길이로 문자열 압축이 가능한지를 구하면 되었다. 그런데 여기서 주의해야 할 부분이 문제 설명이 아닌 문제와 함께 포함된 예제 5에 있는 부분이었다. 아래가 그 예제인데

 

주어진 문자열 s	결과
"xababcdcdababcdcd"	17

입출력 예 #5

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

 

여기서 보면 알듯이 주의해야할 제약조건으로 주어진 문자열을 정한 unit 길이로만 잘라내야 한다는 것이다.

길이를 10으로 잡았다면 주어진 문자열을 앞에서부터 10개씩 잘라내서 확인해야 한다는 것. 이 제약조건이 없다면 문제는 조금 더 복잡해졌을 것이다.

 

여기까지 이해를 했다면 나머지 코드는 생각보다 단순?하게 작성할 수 있었다. 코드에 이해를 돕기위해 주석으로 설명을 붙여놓았다.

 

코드

 

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        //i는 비교의 기준이 되는 단위 문자열 unit의 길이를 의미한다.
        //처음엔 1글자씩 unit을 잡고 차례로 최대 길이/2 만큼 증가시킨다.
        for(int i=1; i<=s.length()/2; i++) {
            int ptr = 0;
            
            //tempLeng은 단위 i일때 압축되는 길이를 저장할 변수, 일단 s의 길이로 초기화
            int tempLeng = s.length();
            
            //문자열 s에서 ptr위치부터 ptr+1이전까지를 잘라 unit에 저정한다.
            for(;ptr+i<=s.length();) {
                String unit = s.substring(ptr, ptr+i);
                ptr += i;
                //count는 현재 단위 문자열 unit이 몇개나 반복되는지를 저장한다.
                int count = 0;
                
                //단위 문자열인 unit부터 다음 i개 문자가 일치하는지 확인한다.
                for(;ptr+i<=s.length();) {
                    //unit과 unit다음 i개의 문자가 일치하면 count를 증가시킨다.
                    if(unit.equals(s.substring(ptr,ptr+i))) {
                        count++;
                        ptr += i;
                    } else {
                        //만약 unit과 다르다면 바로 unit을 다음 i개의 문자로 갱신하기 위해 반복문을 빠져나간다.
                        break;
                    }
                }
                
                //unit을 갱신하기 전에 이번 unit으로 몇 개나 반복되었는지 확인하고, 암축된 길이만큼 tempLeng의 값을 감소시킨다.
                if(count>0) {
                    tempLeng -= i*count;
                    
                    //반복된 글자수만큼 숫자가 들어가기 때문에 tempLeng은 삽입되는 숫자 갯수만큼 다시 증가한다.
                    //count를 1 증가시키는 이유는 count가 9라면 실제로는 unit+unit*9 이므로 10unit과 같이 표현되기 때문이다.
                    count++;
                    while(count>0) {
                        count/=10;
                        tempLeng++;
                    }
                }
            }
            
            //unit의 길이가 i일때 압축가능한 길이와 이전 answer에 저장되어 있던 이전 최소압축길이를 비교해 answer을 갱신한다.
            answer = Math.min(answer, tempLeng);
        }
        
        return answer;
    }
}