[ 프로그래머스- 2020카카오 공채 ] 문자열 압축 (java)

프로그래머스 2020 카카오 공채 문자열 압축 (자바)

문자열 s에서 연속으로 반복해서 나타나는 구간을 압축하는데, 가장 많이 압축했을 때 길이 구하기 

aaaccc -> 3a3c (단위1)

aabbaccc -> aabba3c (단위1)

 

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

카카오 공채 7문제 중 첫 번째 문제로 정답률 25.9%

 

문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악

• 문자열 자르기
• 부분 문자열 얻기
• 문자열 비교하기
• 문자열 길이 얻기

 

방법 1 

압축 문자열을 만들고 그 문자열의 최솟값을 구하는 방법

이 방법은 중간에 출력해서 오류 찾기가 좋지만, 문제는 최소 길이를 구하는 것으로 중간에 압축 문자열을 구하는 것은 추가적인 시간낭비가 된다. 

 

 

방법 2

방법 1에서 압축 문자열을 만들지 않고 전체 길이만 계산하는 방법

방법 1에서 단순히 압축할 문자열과 반복 수만 고려해서 전체 길이를 계산한다. 

 

 

핵심: 압축

모든 단위, 1 ~ 문자열 길이 절반 까지 압축을 시도해봐야한다. 

 

압축하는 방법은 단위 크기의 문자열과 그 문자열의 반복 수를 구하면 된다. 

ex) ababab 를 단위 2일때, 문자열 ab의 반복 수는 3이다. => 3ab 로 압축된다. 

 

따라서, 문자열에서 unit크기 만큼 잘라 비교한다. 

자를 unit은 start와 end 변수로 영역을 표시했다. 

 

 

현재 자른 문자열과 다음에 자를 문자열을 비교한다. 

 - 같다면? 반복 수 ++;

 - 다르면? 현재 문자열의 압축길이를 구한다. ( 현재 문자열 길이 + 반복 수 길이 )

 

 

주의 

1. 비교 후, 마지막에 남은 문자열 길이도 고려하기 

abababcde라면, 3abcde로 압축될 수 있다. 

그런데, ab압축만 고려하고 cde는 고려하지 않는 경우를 주의해야 한다. 

 

 

2. 마지막, 반복 문자열 고려하기 

ababcdcdcd라면, 2ab3cd로 압축될 수 있다. 

그런데, 길이를 고려하는 시점이 다음 문자열과 다를 때 이므로, 마지막 cd는 루프 밖에서 고려해줘야한다. 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

** 이전에 작성한 코드가 많이 부족해서 다시 작성했습니다! ** 

 

 

 

코드

public class Solution {
    public int solution(String s) {
         int minLen = s.length();
        // unit 단위만큼 검사 
        for(int unit = 1 ; unit <= s.length()/2 ; unit++) {
            // 검사할 문자의 범위 start ~ end 
            int start = 0;
            int end = start + unit;
            int compressedLen = 0;
            int repeatedCnt = 1;
            
            // unit만큼 자른 첫 문자열  
            String curWord = s.substring(start, end);
            String nextWord;
            
            start += unit;
            end += unit;
            
            // 문자열 끝까지 검사 
            while(end <= s.length()) {
                nextWord = s.substring(start ,end);
                
                // next가 cur와 달라지게 될때, cur의 압축 길이를 compressedLen에 더한다.  
                if(!curWord.equals(nextWord)) {
                    
                    // 반복이 1 넘으면, 압축 수를 길이에 고려 
                    if(repeatedCnt > 1) {
                        compressedLen +=  (int)(Math.log10(repeatedCnt)+1);
                    }
                    compressedLen += curWord.length();
                    
                    repeatedCnt = 0;
                    curWord = nextWord;
                }
                
                repeatedCnt++;
                start += unit;
                end += unit;
            }
            
            // while문을 빠져나가며 고려되지 않은 남은 압축 길이 추가 
            end -= unit;
            compressedLen += s.substring(end).length();
            
            // while문을 빠져나가며 고려되지 않은 마지막 압축 문자열 길이 추가  
            if(repeatedCnt > 1) {
                compressedLen += (int)(Math.log10(repeatedCnt)+1);
            }
            compressedLen += curWord.length();
            
            if (  minLen > compressedLen) {
                minLen = compressedLen;
            }
        }
 
        return minLen;
    }
}