문자열의 아름다움

문제 보기 · Level 5 · 월간 코드 챌린지 시즌1 · 정답률 3% · 푼 사람 269명 (2026-09-30 기준)¹

문제

문자열의 아름다움은 서로 다른 글자가 놓인 두 위치 사이 거리의 최댓값이다. 모든 글자가 같으면 0이다. 예를 들어 “abbca”는 1번 b와 4번 a, 또는 0번 a와 3번 c를 골라 3이다. 소문자 문자열 s의 모든 부분 문자열에 대해 아름다움을 더한 값을 돌려준다.

s 길이 1 ~ 300,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념

누적 합: 같은 글자가 연달아 나온 덩어리끼리 짝을 지어 값을 빼야 한다. 짝이 너무 많을 때, 덩어리 길이를 정렬하고 앞에서부터 합을 쌓아 두면 짝마다 따로 계산하지 않고 한 번에 뺄 수 있다.

수열과 합의 기호: 3단계에서 f(p, q)를 닫힌 식으로 바꿀 때, b에 대한 합을 b ≤ a와 b > a로 끊고 1부터 p까지의 합 p(p + 1)/2와 제곱의 합 p(p + 1)(2p + 1)/6을 쓴다.

순열과 조합: 글자 사이 경계에 0 ~ n 번호를 붙이면, 부분 문자열은 시작 경계와 끝 경계 두 개로 정해지고 (길이 − 1)은 그 사이 안쪽 경계의 수다. 그래서 모든 부분 문자열의 (길이 − 1) 합은 경계 n + 1개 중 셋을 고르는 수 \(\binom{n+1}{3}\)이다.

함께 보면 좋은 수학: 합의 계산과 어림(거듭제곱의 합 공식), 합 ↔ 적분(끝 위치 j(0부터 센다)마다 (길이 − 1)의 합 j(j + 1)/2를 더해도 같은 \(\binom{n+1}{3}\)이 나온다. 이웃한 두 수의 곱을 더하는 이 공식은 \(\int_0^n x^2\,dx = n^3/3\)에 대응한다)

1단계 · 작은 예로 손으로 풀기

“baby”의 부분 문자열 10개를 보면 아름다움은 이렇다.

부분 문자열	b	ba	bab	baby	a	ab	aby	b	by	y
길이 − 1	0	1	2	3	0	1	2	0	1	0
아름다움	0	1	1	3	0	1	2	0	1	0

양 끝 글자가 다르면 아름다움은 길이 − 1이다. 양 끝이 가장 먼 두 위치이기 때문이다.
“bab”처럼 양 끝 글자가 같을 때만 길이 − 1보다 작아진다.

길이 − 1의 합은 10이고, “bab”에서 1이 모자라 답은 9다.

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

부분 문자열마다 정의대로 아름다움을 구한다. 부분 문자열이 약 \(n^2/2\)개인데, n = 30만이면 450억 개다. 하나씩 보기만 해도 어림없다.

3단계 · 핵심 아이디어

길이 − 1을 먼저 다 더한다: 모든 부분 문자열의 (길이 − 1) 합은 \(\binom{n+1}{3}\)이다. n = 4면 10이다. 여기서 모자란 만큼만 뺀다.
모두 같은 글자인 부분 문자열: 아름다움이 0이라 길이 − 1을 통째로 뺀다. 이런 부분 문자열은 같은 글자 덩어리 하나 안에 있다. 길이 p인 덩어리에서 빼는 양은 \(\binom{p+1}{3}\)이다.
양 끝이 같은 글자 c이고, 사이에 다른 글자가 있는 부분 문자열: 앞쪽에 c가 a개, 뒤쪽에 c가 b개 이어진다고 하자. 첫 글자와 가장 멀리 짝지을 수 있는 다른 글자는 뒤쪽 c 덩어리 바로 앞 글자다. 거리는 (길이 − 1) − b다. 끝 글자와 가장 먼 다른 글자는 앞쪽 c 덩어리 바로 뒤 글자다. 거리는 (길이 − 1) − a다. 다른 짝은 이 둘보다 가깝다. 그래서 아름다움은 (길이 − 1) − min(a, b)다. “aabaa” 전체는 a = b = 2라 4 − 2 = 2다.
덩어리 짝으로 묶기: 이런 부분 문자열은 c 덩어리 하나(길이 p) 안에서 시작해, 뒤쪽의 다른 c 덩어리(길이 q) 안에서 끝난다. 시작 위치를 덩어리 안에서 옮기면 a가 1부터 p까지 한 번씩, 끝 위치를 옮기면 b가 1부터 q까지 한 번씩 나온다. 그래서 두 덩어리의 짝마다 빼는 양은 다음과 같다(p ≤ q).

\[f(p, q) = \sum_{a=1}^{p} \sum_{b=1}^{q} \min(a, b) = \frac{p(p+1)(3q+1-p)}{6}\]

a를 하나 고정하면(a ≤ p ≤ q), b가 1 ~ a일 때 min은 b이고 b가 a + 1 ~ q일 때 min은 a다. 그래서 b에 대한 합은 a(a+1)/2 + a(q − a)다. 이것을 a = 1 ~ p로 더하면 p(p+1)(p+2)/6 + q·p(p+1)/2 − p(p+1)(2p+1)/6 = p(p+1)(3q+1−p)/6이다. 예를 들어 f(1, 1) = 1, f(2, 2) = 5, f(2, 3) = 8이다.

누적 합으로 짝을 한 번에: f는 p와 q를 바꿔도 같으니, 덩어리가 문자열 어디에 있는지는 상관없고 길이만 중요하다. f(p, q) = A(p) + q·B(p) 꼴이다. 여기서 A(p) = p(p+1)(1−p)/6, B(p) = p(p+1)/2다. 글자마다 덩어리 길이를 정렬하고 A와 B의 누적 합을 쌓아 가면, 새 길이 q마다 “앞의 모든 덩어리와의 짝”을 A합 + q·B합으로 한 번에 뺀다.

4단계 · 코드 흐름

total = \(\binom{n+1}{3}\).
문자열을 같은 글자 덩어리로 자른다. 덩어리 길이 p마다 \(\binom{p+1}{3}\)을 빼고, 그 글자의 목록에 p를 넣는다.
글자마다 길이 목록을 정렬한다. s1 = s2 = 0에서 시작해, 길이 q마다 total에서 s1 + q·s2를 빼고 s1에 A(q), s2에 B(q)를 더한다.
total을 돌려준다.

5단계 · 파이썬 코드

from collections import defaultdict

def solution(s):
    n = len(s)
    total = (n + 1) * n * (n - 1) // 6       # 모든 부분 문자열의 (길이 − 1) 합
    runs = defaultdict(list)                  # 글자 → 덩어리 길이들
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        p = j - i
        total -= (p + 1) * p * (p - 1) // 6   # 한 덩어리 안의 부분 문자열은 아름다움 0
        runs[s[i]].append(p)
        i = j
    for lens in runs.values():
        lens.sort()
        s1 = s2 = 0                           # 앞에서 본 덩어리들의 A합, B합
        for q in lens:
            total -= s1 + q * s2              # 앞의 덩어리 p(≤ q)마다 f(p, q)를 뺀다
            s1 += q * (q + 1) * (1 - q) // 6
            s2 += q * (q + 1) // 2
    return total

(n + 1) * n * (n - 1) // 6: 이어진 세 수의 곱은 늘 6의 배수라 나눗셈이 딱 떨어진다.
lens.sort(): f(p, q) = A(p) + q·B(p)는 p ≤ q일 때의 식이다. 정렬해야 앞에 쌓인 길이가 모두 q 이하다.
q * (q + 1) * (1 - q) // 6: 0 이하인 값이다. 6의 배수라 음수여도 //가 정확히 나눈다.

6단계 · 실행 추적

“aabaa”다. n = 5라 처음 total은 \(\binom{6}{3}\) = 20이다. 덩어리는 aa, b, aa다.

하는 일	빼는 값	total
덩어리 aa (p = 2)	\(\binom{3}{3}\) = 1	19
덩어리 b (p = 1)	0	19
덩어리 aa (p = 2)	1	18
글자 a의 첫 길이 q = 2	s1 + 2·s2 = 0	18
(s1 = A(2) = −1, s2 = B(2) = 3이 된다)
글자 a의 둘째 길이 q = 2	−1 + 2·3 = 5 = f(2, 2)	13
글자 b의 길이 q = 1	0	13

답은 13이다. 부분 문자열 15개의 아름다움을 하나씩 더해도 13이다.

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

덩어리 자르기가 \(O(n)\), 정렬이 \(O(n \log n)\)이다. 30만 글자 네 가지(무작위, 한 글자뿐, ab 반복, 덩어리 길이가 1, 2, 3, …으로 다 다른 문자열)를 합쳐 0.1초쯤 걸렸다.

양 끝 글자가 같으면 무조건 1만 뺀다. “aabaa” 전체의 아름다움은 4 − 1 = 3이 아니라 2다.
모두 같은 글자인 부분 문자열의 길이 − 1을 빼는 것을 잊는다.
같은 글자의 덩어리 짝을 이중 반복으로 모두 돈다. ab가 15만 번 반복되면 a 덩어리만 15만 개라 짝이 110억 개가 넘는다.
답은 n = 30만이면 약 \(4.5 \times 10^{15}\)까지 커진다. 파이썬은 괜찮지만 다른 언어는 64비트 정수를 써야 한다.

검증: 문제의 예시 2개, 6단계 표, f의 식(p, q ≤ 8에서 이중 합과 비교)을 코드로 확인했다. 무작위 문자열 3,000개(14글자 이하)에서 “부분 문자열마다 정의대로 아름다움을 구하는” 풀이와 결과가 같았다. 30만 글자의 시간도 쟀다 — 19_pg68938_p1.py

프로그래머스 스쿨, “문자열의 아름다움” (https://school.programmers.co.kr/learn/courses/30/lessons/68938), 2026-10-01 조회. ↩