문제 보기 · Level 2 · 2020 KAKAO BLIND RECRUITMENT · 정답률 45% · 푼 사람 34,388명 (2026-09-30 기준)1

문제

문자열을 길이 k 단위로 잘라, 같은 조각이 연달아 나오면 “개수+조각”으로 줄인다. 개수가 1이면 숫자를 쓰지 않고, 끝에 남는 짧은 조각은 그대로 붙인다. 모든 k에 대해 압축한 결과 중 가장 짧은 길이를 돌려준다.

  • s 길이 1~1,000, 소문자만

풀이

막히면 한 단계씩 펼친다.

필요한 개념
1단계 · 작은 예로 손으로 풀기

“abab”

  • k = 1: a, b, a, b → 이어진 같은 조각이 없다 → “abab” (4)
  • k = 2: ab, ab → “2ab” (3)
  • k = 3: aba, b → “abab” (4)
  • k = 4: abab → “abab” (4)

가장 짧은 것은 3이다. 조각은 이어져 나와야 줄어든다.

2단계 · 가장 단순한 방법과 그 속도

k를 1부터 n까지 모두 해 본다. k마다 문자열을 한 번 훑으니 n번이고, 모두 n × n = 100만 번이다. 된다.

k가 n/2보다 크면 같은 조각이 두 번 나올 수 없어 압축되지 않는다. 그래서 k는 n // 2까지만 봐도 되고, 답은 처음에 n(압축하지 않은 길이)으로 둔다.

3단계 · 핵심 아이디어

k마다:

  1. k글자씩 잘라 조각 리스트를 만든다(끝 조각은 짧을 수 있다).
  2. 앞에서부터 같은 조각이 몇 번 이어지는지 센다.
  3. 이어짐이 끝날 때마다 길이에 (조각 길이 + 개수의 자릿수)를 더한다. 개수가 1이면 자릿수는 0이다. 개수가 10 이상이면 자릿수가 2 이상이라는 점에 주의한다(len(str(개수))).

2 이상인 개수 c를 적는 글자 수는 c의 10진 자릿수 \(\lfloor \log_{10} c \rfloor + 1\)이다.

4단계 · 코드 흐름
  1. 답을 len(s)로 둔다.
  2. k = 1 … len(s) // 2마다:
    • 조각 리스트를 만든다.
    • 조각을 차례로 보며 앞 조각과 같으면 개수 +1, 다르면 지금까지의 묶음 길이를 더하고 개수를 1로.
    • 마지막 묶음도 더한다.
    • 답을 더 작은 값으로 고친다.
5단계 · 파이썬 코드 
def solution(s):
    best = len(s)
    for k in range(1, len(s) // 2 + 1):
        chunks = [s[i:i + k] for i in range(0, len(s), k)]
        length, count = 0, 1
        for a, b in zip(chunks, chunks[1:] + [None]):   # 이웃한 두 조각
            if a == b:
                count += 1
            else:                                        # 이어짐이 끝났다
                length += len(a) + (len(str(count)) if count > 1 else 0)
                count = 1
        best = min(best, length)
    return best
  • range(0, len(s), k): 0, k, 2k, …에서 자른다.
  • zip(chunks, chunks[1:] + [None]): (조각, 다음 조각)을 짝짓는다. 끝에 None을 붙여 마지막 조각도 “다음과 다르다”로 끝나게 한다.
  • len(str(count)): 개수 12는 “12”라 두 글자다.
6단계 · 실행 추적

“ababcdcdababcdcd” (길이 16)

k 압축 결과 길이
1 줄어드는 곳 없음 16
2 2ab2cd2ab2cd 12
4 abab, cdcd, abab, cdcd → 이어진 같은 조각이 없음 16
8 2ababcdcd 9

가장 짧은 9가 답이다.

7단계 · 복잡도와 흔한 실수

k마다 \(O(n)\), k가 n/2개라 \(O(n^2)\)다.

  • 개수의 자릿수를 늘 1로 센다. 10번 이상 이어지면 틀린다.
  • k를 n까지 보지 않아 길이 1짜리 문자열에서 답을 못 구한다. 이 코드는 답을 처음부터 len(s)로 두어 해결했다.
  • 끝의 짧은 조각을 빼먹는다.
검증: 문제의 예시 5개를 통과했고, 반복이 많은 무작위 문자열 3,000개에서 “k마다 압축 문자열을 실제로 만들어 길이를 재는” 풀이와 결과가 같았다. 같은 조각이 10번 이상 이어지는 경우도 넣었다 — 16_pg60057_p1.py

  1. 프로그래머스 스쿨, “문자열 압축” (https://school.programmers.co.kr/learn/courses/30/lessons/60057), 2026-09-30 조회. ↩