프로그래머스 - 문자열 압축 (Level 2)

너무 어려워서 풀지 못했다.

수많은 도전을 했지만 실패...

도통 모르겠다.

class Solution {
    public int solution(String s) {
        int len=s.length();
        String s1="";
        String s2="";
        int count=1;
        String str=s;
        int answer=str.length();
        for(int i=0;i<len/2;i++){
            StringBuilder sb=new StringBuilder();
            for(int j=i+1;j<len;j++){
                s1=s.substring(i,j);
                s2=s.substring(i+1,j+1);
                if(s1.equals(s2)) { //같다면
                    count++;
                }
                else{ //다르다면
                    if(count!=1) {// count가 0이 아니라면
                        sb.append(Integer.toString(count)).append(s1);
                    }
                    else {
                        sb.append(s1);
                    }
                }
            }
            if(str.length()>sb.toString().length()){
                str=sb.toString();
                answer=str.length();
            }
        }
        return answer;
    }
}

 

---

책에서의 풀이

 

: 1. 1부터 s의 길이만큼 자를 문자열의 길이를 설정하며 반복

2. 설정된 길이만큼 문자열을 잘라서 token 배열에 담기

3. token 배열에 담긴 문자열을 비교하며 하나의 문자열로 압축 

4. 1~3  과정으로 압축된 문자열 중 가장 짧은 길이 반환

 

import java.util.ArrayList;
import java.util.List;

public class 문자열_압축 {
    private List<String> split(String source, int length) { //압축하기 위해 length 길이씩 문자열을 잘라 리스트에 담아주는 메소드
        List<String> tokens = new ArrayList<>();

        for (int startIndex = 0; startIndex < source.length(); startIndex += length) {
            //문자열을 자르는 시작 인덱스는 0부터 시작하여 length만큼씩 증가
            int endIndex = startIndex + length; //substring의 두번째 인자
            if (endIndex > source.length()) endIndex = source.length(); //endIndex가 문자열 길이 밖으로 벗어나면 조정
            tokens.add(source.substring(startIndex, endIndex)); //문자열 잘라 리스트에 추가
        }
        return tokens;
    }

    private int compress(String source, int length) { //문자열을 압축하고, 압축된 문자열의 길이를 반환하는 메소드
        StringBuilder builder = new StringBuilder();

        String last = ""; //직전에 등장한 문자열 담는 변수
        int count = 0; //등장 횟수 세는 변수
        for (String token : split(source, length)) {
            if (token.equals(last)) { //직전에 등장한 문자열과 같다면 등장 횟수 증가
                count++;
            } else { //직전에 등장한 문자열과 다르다면
                if (count > 1) builder.append(count); //count가 1보다 크면 압축 문자열에 포함
                builder.append(last); //count가 1보다 같거나 작으면 직전 문자만 담기
                last = token; //last를 현재 문자열로 초기화
                count = 1; //등장 횟수 1로 초기화
            }
        }
        //마지막 문자열 담아야 함.
        if (count > 1) builder.append(count);
        builder.append(last);

        return builder.length();
    }

    public int solution(String s) {
        int min = Integer.MAX_VALUE; //최솟값을 저장할 변수
        for (int length = 1; length <= s.length(); length++) { 
        //1부터 문자열 s의 길이만큼 자를 문자열의 길이를 설정
        //s의 길이가 1인 경우를 위해 s.length()/2까지 하지 않음.
            int compressed = compress(s, length);
            if (compressed < min) { //가장 짧은 압축 길이를 찾기
                min = compressed;
            }
        }
        return min;
    }
}