문자열 압축 (Java)

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

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

 

프로그래머스 2020 KAKAO BLIND RECRUITMENT "문자열 압축" 문제 풀이이다.

 

처음 문제를 읽을 때 abcabcdede가 3abc2de와 같이 압축되어야 하는 줄 알고 헤메다가 다른 분들 풀이를 조금 참고했다.

주어진 문자열을 3개 짜리, 2개 짜리 처럼 기준이 여러 개가 아니라 문자열을 자를 수 있는 단위는 하나로 고정되어 있으니 주의해야 한다.

 

문자열을 자를 수 있는 단위가 하나로 고정되어 있다는 점, 문자열을 제일 앞에서부터 잘라야 한다는 점을 활용해 문자열을 자르는 단위별로 압축할 경우 그 크기를 구하고 가장 압축률이 높은 경우를 찾아냈다.

 

접근법 및 소스코드는 아래와 같다.

 

 

class Solution {
    public int solution(String s) {
        int answer = 0;
        if (s.length() == 1) {
            return 1;
        }
        // 1 ~ N/2+1 중에 문자열을 몇 개 단위로 자를지 반복
        for (int i = 1; i < s.length() / 2 + 1; i++) {
            String target = s.substring(0, i);  // 문자열을 N개 단위로 쪼개어 비교할 대상
            String done = "";                   // 반복되지 않는 문자열이거나 이미 압축된 문자열
            String current = "";                // 현재 비교되는 대상
            int count = 1;                      // 반복 횟수
            
            // N개 단위로 자르면 그 다음 N개와 비교
            for (int j = i; j < s.length(); j += i) {
                // 남은 문자열이 N개보다 작을 때는 압축 불가능하므로 누적하고 끝냄
                if (j + i > s.length()) {
                    done += s.substring(j, s.length());
                }
                // 남은 문자열이 N개 이상일 경우는 다음 N글자와 비교 후 반복횟수 증가 또는 반복대상 변경
                else {
                    current = s.substring(j, j + i);
                    if (current.equals(target)) {
                        count++;
                    } else {
                        done += ((count == 1 ? "" : count + "") + target);
                        target = s.substring(j, j + i);
                        count = 1;
                    } 
                }
            }
            // 순서는 상관없으므로
            // 반복횟수와 대상(마지막으로 반복된 대상), 이미 압축되었거나 압축되지 못하는 문자열들을 합침
            String result = (count == 1 ? "" : count + "") + target + done;

            // N개 단위 중 어떤 문자열이 가장 짧은지 비교하여 최소값 구함
            if (answer == 0) {
                answer = result.length();
            }
            if (result.length() < answer) {
                answer = result.length();
            }
        }
        return answer;
    }
}