[Programmers / Level2] 문자열 압축(Java)

💡 Info

• 난이도: Lv2
• 시간 제한: 1초
• 메모리 제한: 128MB
  프로그래머스 링크: https://programmers.co.kr/learn/courses/30/lessons/60057
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/60057. 문자열 압축

💭 문제 이해

• 압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return하기
  • 입출력 예시
    

💭 생각한 알고리즘

실제 풀이 시간 : 27분

• s 입력받기
• 문자열을 1개 ~ n개까지 자르기(or 문자열 반복 찾기)
• 그 중 가장 짧은 길이 출력하기

class Solution {
    public int solution(String s) {
        
        int answer = s.length();

        for(int i = 1; i<s.length() / 2 + 1; i++){
            int compressLength = compress(s, i);
            answer = Math.min(answer, compressLength);
        } 
        return answer;
    }
    
    public int compress(String s, int unit){
        StringBuilder compressDone = new StringBuilder();
        String now = "";
        int count = 1;
        
        for (int j = 0; j <= s.length(); j += unit) {
            int start = j;
            int end = Math.min(j + unit, s.length());

            String sub = s.substring(start, end);

            if (now.equals(sub)) {
                count++;
            } else {
                if (count > 1) {
                    compressDone.append(count);
                }
                compressDone.append(now);
                now = sub;
                count = 1;
            }
        }
        return compressDone.length();
    }
}

❌ 오답체크

• 5개 중 2개만 정답
  

• 문자열을 끝까지 제대로 처리하지 않아 길이가 더 길게 측정된 것으로 파악 -> 문자열 처리 코드를 한번 더 추가해서 처리 완료하기

if (count > 1) {
	compressDone.append(count);
}
compressDone.append(now);
return compressDone.length();

💭 최종 풀이

• 주어진 문자열의 길이로 초기화하기
• 문자열을 1 ~ n개까지 자르면서 압축된 문자열 중 가장 짧은 길이 찾기
• 압축하는 클래스 별도 생성해 계산하기

class Solution {
    public int solution(String s) {
        /*
        - s 입력받기
        - 문자열을 1개 ~ n개까지 자르기(or 문자열 반복 찾기)
        - 그 중 가장 짧은 길이 출력하기
        */
        int answer = s.length();

        //문자열을 1개 ~ n개까지 자르기(or 문자열 반복 찾기)
        for(int i = 1; i<s.length() / 2+1; i++){
            int compressLength = compress(s, i);
            answer = Math.min(answer, compressLength);
        } 
        return answer;
    }
    
    public int compress(String s, int unit){
        StringBuilder compressDone = new StringBuilder();
        String now = "";
        int count = 1;
        
        for (int j = 0; j <= s.length(); j += unit) {
            int start = j;
            int end = Math.min(j + unit, s.length());

            String sub = s.substring(start, end);

            if (now.equals(sub)) {
                count++;
            } else {
                if (count > 1) {
                    compressDone.append(count);
                }
                compressDone.append(now);
                now = sub;
                count = 1;
            }
        }
        
        if (count > 1) {
            compressDone.append(count);
        }
        compressDone.append(now);
        
        return compressDone.length();
    }
}