문제 개요
문자열 s가 주어졌을 때, 해당 문자열의 모든 부분 문자열(substring)에 대한 '아름다움(beauty)' 값의 합을 구하는 것이 목표입니다.
여기서 문자열의 아름다움이란 가장 많이 등장한 문자의 빈도에서 가장 적게 등장한 문자의 빈도를 뺀 값을 의미합니다. 예를 들어 문자열이 "abaacc"라면, 'a'는 3번, 'b'와 'c'는 각각 1번 등장하므로 아름다움은 3 - 1 = 2가 됩니다.
예시
입력이 s = "xxyzy"라고 가정해 보겠습니다. 이 경우 출력값은 5입니다. 그 이유는 아름다움 값이 0이 아닌 부분 문자열이 ["xxy", "xxyz", "xxyzy", "xyzy", "yzy"]로 총 5개이며, 각 부분 문자열의 아름다움 값이 모두 1이기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다:
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- 바깥쪽 반복문으로 시작 인덱스 i를 순회합니다.
- 안쪽 반복문으로 끝 인덱스 j를 순회하며 부분 문자열을 생성합니다.
- s[i]부터 s[j]까지 구간의 문자 빈도를 담은 맵(Counter) c를 만듭니다.
- c의 모든 빈도 값을 리스트 v로 추출합니다.
- res에 (v의 최댓값 - v의 최솟값)을 누적하여 더합니다.
- 모든 반복이 종료되면 res를 반환합니다.
길이가 1 또는 2인 부분 문자열은 아름다움 값이 항상 0이므로, 탐색 범위에서 제외하여 약간의 최적화를 적용할 수 있습니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다:
from collections import Counter
def solve(s):
res = 0
for i in range(len(s)):
for j in range(i + 2, len(s)):
c = Counter(s[i:j+1])
v = c.values()
res += (max(v) - min(v))
return res
s = "xxyzy"
print(solve(s))
입력
"xxyzy"
출력
5
복잡도 분석
이 방법은 가능한 모든 부분 문자열 조합을 확인하므로 시간 복잡도는 대략 O(n³)입니다. 부분 문자열의 개수가 O(n²)개이고, 각 부분 문자열의 빈도를 계산하는 데 O(n)이 소요되기 때문입니다. 공간 복잡도는 부분 문자열별 빈도 맵을 저장해야 하므로 O(n)입니다. 문자열이 매우 길다면 슬라이딩 윈도우나 누적 빈도 배열 등의 기법으로 최적화할 수 있습니다.