[프로그래머스 Lv.2] 문자열 압축(Java) - 완전탐색

📌 핵심 요약

• 탐색 범위는 1 ~ n/2 — n/2를 포함해야 한다.

 

목차

1 문제 정리

Programmers #60057

문자열 압축

1 ≤ s.length() ≤ 1000

난이도: Level 2

문자열을 앞에서부터 일정한 단위로 잘라, 같은 조각이 연속으로 반복되면 반복 횟수 + 조각 형태로 압축한다. 단위 길이를 1 이상 자유롭게 정할 수 있을 때, 압축한 결과 중 가장 짧은 것의 길이를 반환한다.

압축 규칙

1. 단위 길이 k를 정하고 문자열을 앞에서부터 k글자씩 자른다.
2. 직전 조각과 같은 조각이 연속되면 개수를 센다.
3. 다른 조각이 나오면 (개수)(조각) 형태로 기록한다. 개수가 1이면 숫자는 붙이지 않는다.
4. 마지막 조각은 k보다 짧을 수 있으며, 그대로 남긴다.

2 완전탐색으로 방향을 정했다

k 하나하나를 전부 시도하는 것 말고는 방법이 없다고 판단했다. 범위와 복잡도를 따져보면 충분히 감당 가능하다.

항목	값	근거
탐색 범위	k = 1 ~ n/2	절반을 넘는 단위는 두 번 이상 반복될 수 없어 압축이 불가능하다
k당 비용	O(n)	n/k번 비교 × 비교 1회당 O(k)
전체	O(n²)	n=1000이면 최악 10⁶ 수준

ℹ️

제한이 곧 힌트다

s.length() ≤ 1000이라는 제한 자체가 "전부 다 돌려봐도 된다"는 출제자의 신호라고 봤다. 제한이 10⁵ 이상이었다면 Z-알고리즘이나 해싱 기반 주기 판별을 고민해야 했을 것이다.

4 처음 작성한 코드와 경계 버그

   

Java — 첫 시도 (오답)

class Solution {
    public int solution(String s) {
        if (s.length() == 1) return 1;

        int answer = s.length();

        for (int i = 1; i < s.length() / 2; i++) {   // ← 문제의 경계
            StringBuilder sb = new StringBuilder();
            String ss = s.substring(0, i);
            int count = 1;

            for (int j = i; j < s.length(); j += i) {
                String target = "";
                // 범위를 벗어나지 않도록 처리
                if (j + i > s.length()) {
                    target = s.substring(j);
                } else {
                    target = s.substring(j, j + i);
                }

                if (ss.equals(target)) {
                    count++;
                } else {
                    if (count > 1) sb.append(count);
                    sb.append(ss);
                    ss = target;
                    count = 1;
                }
            }

            if (count > 1) sb.append(count);
            sb.append(ss);

            answer = Math.min(answer, sb.length());
        }

        return answer;
    }
}

n/2가 범위에서 빠졌다

바깥 루프 조건이 i < s.length()/2여서 i가 n/2에 도달하지 못한다. 단위 길이가 정확히 n/2일 때는 문자열이 두 조각으로 나뉘고, 두 조각이 같으면 "2" + 앞쪽 절반으로 압축된다. 이 경우가 최적해인 입력이 실제로 존재한다.

입력	n	최적 k	기대값	첫 시도 결과
"ababcdcdababcdcd"	16	8 (= n/2)	9	16
"aaa"	3	1	2	3

"aaa"는 더 극단적이다. n/2 == 1이므로 i < 1이 되어 루프가 한 번도 돌지 않는다. 압축을 아예 시도하지 않은 채 원본 길이 3을 그대로 반환한다. 두 케이스 모두 문제의 예시 입력에 이미 들어 있었다.

⚠️

부등호 하나가 만든 오답

i <= s.length() / 2로 고치면 두 케이스가 동시에 해결된다. 범위를 정할 때 "끝값이 유효한 후보인가"를 반드시 확인해야 한다고 판단했다.

5 길이만 세는 방식으로 개선

경계만 고쳐도 통과하지만, 코드를 다시 보니 불필요한 작업이 하나 있었다. 필요한 것은 sb.length() 하나인데 그 값을 얻으려고 매 k마다 최대 1000자짜리 문자열을 조립하고 있었다. 목적과 수단이 어긋난다고 판단해 길이만 누적하는 방식으로 바꿨다.

   

Java — 최종 풀이

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

        for (int k = 1; k <= s.length() / 2; k++) {
            answer = Math.min(answer, compressedLength(s, k));
        }

        return answer;
    }

    // 단위 길이 k로 압축했을 때의 결과 길이
    private int compressedLength(String s, int k) {
        int len = 0;
        String prev = s.substring(0, k);
        int count = 1;

        for (int i = k; i < s.length(); i += k) {
            String cur = s.substring(i, Math.min(i + k, s.length()));

            if (prev.equals(cur)) {
                count++;
            } else {
                len += digits(count) + prev.length();
                prev = cur;
                count = 1;
            }
        }
        len += digits(count) + prev.length();  // 마지막 패턴

        return len;
    }

    // 1이면 숫자를 안 붙이므로 0자
    private int digits(int count) {
        return count == 1 ? 0 : String.valueOf(count).length();
    }
}

k가 아니라 prev.length()를 더한다

길이를 누적할 때 k가 아니라 prev.length()를 쓴 부분이 중요하다. 꼬리 조각은 k보다 짧을 수 있는데, prev가 그 꼬리일 때 k를 더하면 길이가 실제보다 부풀려진다.

digits()를 분리한 이유

count > 1일 때만 숫자를 붙인다는 규칙이 두 군데에서 반복된다.

그대로 두면 하나의 규칙이 두 곳에 흩어지므로, 이름을 붙여 한 곳으로 모았다.

Math.min(i + k, s.length())으로 if/else 분기를 대체한 것도 같은 맥락이다. 

ℹ️

메서드 분리는 취향의 영역

compressedLength를 분리하면 메인 루프에는 "1 ~ n/2를 훑으며 최솟값을 고른다"는 의도만 남는다. 다만 한 메서드에 다 두면 압축 과정이 위에서 아래로 한 번에 읽히는 장점도 있다. 이 문제는 로직이 짧아 어느 쪽이든 크게 손해 보지 않는다고 본다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.