프로그래머스[Level2] - 문자열 압축 [2020 KAKAO BLIND RECRUITMENT]

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

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

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

 

 

<풀이 방법>

1. 들어온 문자열 s의 절반을 잘라서  1부터 s/2까지 압축 가능 여부 확인하기

(ex. abcabcdede라면 최대로 가능한 압축단위가 5임)

2. 문자열 갯수만큼 for문을 돌고 앞에서부터 압축할 대상 문자열을 뽑기

3. 압축할 기준단위가 되는 문자열이 반복되는지를 확인

4. 반복 된다면.. cnt ++과 비교대상에서 제외(replaceFirst)

5. 반복이 됐든 안됐든 while절이 끝나면 돈만큼 i의 위치를 조정해주기.. (중복방지)

6. 반복된 것이 1개 이상이라면 cnt번호와 함께 문자열 붙여주고 아니라면 그냥 문자열만 붙여준다.

7. 압축 단위 문자열을 나누다가 끝부분이 짤렸을 경우, 붙여주는 작업

(ex. abcabcdede를 3으로 잘라서 확인했을 시.. abc / abc / ded / d 이렇게 d가 빠지기때문에.. 붙여줘야함)

8. 그렇게 완성된 문자열의 길이를 비교해서 가장 짧은 것 선택

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        
        
        //문자열 길이의 절반만큼 돌면서 압축 가능여부 보기
        //단, 문자열 길이가 1일 경우에는 늘 1이다.
        if(s.length()==1)
            answer = 1;
        for(int n = 1 ; n <= s.length()/2 ; n++) {
        
            String ansStr = ""; //완성된 문자열
            String orgStr = new String(s); // 원본 문자열
            
            for(int i = 0; i<s.length();i++) {
                if(i+n > s.length())
                    continue;
                int cnt = 1;
                String compStr = s.substring(i,i+n); // 압축할 대상 문자열
                
                orgStr = orgStr.replaceFirst(compStr,"");
                
                //다음 문자열이 반복되는가?
                while(orgStr.startsWith(compStr)) {
                    cnt ++;
                    orgStr = orgStr.replaceFirst(compStr,"");
                
                }
                
                i = i+(cnt*n)-1; // 해당 for문이 끝나면 i++이 될거니까 미리 빼줌
                if(cnt>1) {
                    ansStr += cnt+compStr;
                }
                else {
                    ansStr += compStr;
                }

            }
            ansStr += s.substring((s.length()/n)*n,s.length()); //n단위로 잘랐을때 남은 뒤에 나머지 값들 붙여주기 
            answer = Math.min(answer,ansStr.length());
            //System.out.println(ansStr);
        }
        
        return answer;
    }
}

 

 

테스트 케이스 5번에서 자꾸 틀려서 서치 해보니..

input = "a" 로 문자열이 하나만 들어올때 처리를 못하고있었다.. 왜냐면 나는 첨부터 문자열 절반을 나눴으니까ㅠ

그래서 문자열 하나만 들어올때 처리를 해주고나니 통과를 했다ㅠ

푸는데 2시간이나 걸렸고, 코드도 지저분하지만 풀이를 전혀 안보고 푼 것에 만족한다~~