[PG] 문자열 압축 - Java

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

코딩테스트 연습 - 문자열 압축

[풀이]

마지막 예제에서 xababcdcdababcdcd 의 경우 맨 앞에서부터 잘라야 한다는 것을 보지 않아서 삽질했다.

x다음부터는 비교를 할 수가 없고, 항상 맨 처음부터 비교해야 함

 

1. 1개 단위로 자를 때, 2개 단위로 자를 때, ... 를 모두 실행한 후 압축한 문자열의 길이를 비교한다.

2. 몇 개 단위까지 자를 수 있을까? => 문자열의 길이(L)/2 까지 자를 수 있다.

   ex) 문자열 길이 7이면 7/2 = 3 , 3까지 자를 수 있음. 4는 어차피 안됨 (4+4는 8이라서 길이 벗어나니까)

3. substring 함수를 사용해서 while문으로 문자열의 끝까지 비교한다. (k++하면서)

   문자열을 벗어나면 break

   3-1. 두 문자열이 같으면 count++; 다르면 zip문자열에 해당 문자열을 더한다. (1이면 그냥 더하고, 1초과면 숫자를 더해서 더함)

4. cash는 while문을 빠져나왔을 때 끝까지 다 갔는지를 확인하기 위함이다. 

   cash == L이면 zipLength에 더해 줄 필요 없고, 다른 경우에는  L%i를 더해준다. 

5. answer 최소 비교하고, 최소 리턴

 

[코드]

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 1000;
        int L = s.length();
        for(int i=1;i<=L/2;i++){ //i : 자르는 단위
            String zip = "";
            int zipLength = 0;

            int k=1;
            int count=1;
            int cash = 0;
            String box1 = "";
            String box2 = "";
            while(true){
                if(i*(k+1)<=L){
                    box1 = s.substring(i*(k-1),i*k);
                    box2 = s.substring(i*k,i*(k+1));

                    if(box1.equals(box2)){
                        count++;
                    }
                    else{
                        if(count==1){
                            zip += box1;
                        }
                        else{
                            zip += count+box1;
                        }
                        count=1;
                    }
                    cash = i*(k+1);
                    k++;
                }
                else{
                    break;
                }
            }
            
            if(count==1){ //마지막꺼 처리
                zip += box2;
            }
            else{
                zip += count+box1;
            }
            
            if(cash!=L){
                zipLength += (L%i==0)?(i):(L%i); //딱 맞게 끝난 애가 아니면 짜투리 추가하기    
            }

            zipLength += zip.length();
            answer = Math.min(answer,zipLength);
        }
        
        if(answer == 1000){ //한 번도 비교 안한 애면 길이가 1인 애
            answer = 1;
        }
        return answer;
    }
}

[느낀점]

소요시간 : 3h

왜이렇게 어렵지? 문자열 너무 어렵네.. 

문자열 대비를 좀 더 해야겠다

substring(start,end)도 오랜만에 본 느낌