문제 개요
회사 이름이 문자열로 주어졌을 때, 해당 이름에서 가장 자주 등장하는 세 글자를 찾아 출력하는 프로그램을 만들어 보겠습니다. 이때 다음과 같은 규칙을 따라야 합니다.
- 빈도수가 가장 높은 세 글자를 선택합니다.
- 선택한 글자들을 빈도수 기준 내림차순으로 정렬합니다.
- 만약 여러 글자의 빈도수가 같다면, 알파벳 순서를 우선하여 정렬합니다.
예를 들어 입력 문자열이 s = "TUTORIALSPOINT"라면, 출력 결과는 [[3, 'T'], [2, 'I'], [2, 'O']]가 됩니다. 즉, 'T'가 세 번, 'I'와 'O'가 각각 두 번씩 등장하기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 먼저 x := 문자열 s에 포함된 글자와 그 빈도수를 담은 맵(딕셔너리)을 생성합니다.
- res := 결과를 저장할 새로운 리스트를 만듭니다.
- x의 각 요소 i에 대해 [빈도수, 글자] 형태의 쌍을 res에 추가합니다.
- res를 알파벳 순서(글자 기준)로 먼저 정렬합니다.
- 이어서 res를 빈도수 기준 내림차순으로 다시 정렬합니다. 이렇게 두 번 정렬하면 빈도수가 같은 글자들은 알파벳 순서가 유지됩니다.
- 마지막으로 res에서 처음 세 개의 항목을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해할 수 있습니다.
from collections import Counter
def solve(s):
x = Counter(s)
res = []
for i in x:
res.append([x[i], i])
res = sorted(res, key=lambda cnt: cnt[1])
res = sorted(res, key=lambda cnt: cnt[0], reverse=True)
return res[:3]
s = "TUTORIALSPOINT"
print(solve(s))
위 코드에서는 collections 모듈의 Counter 클래스를 활용해 각 글자의 빈도수를 손쉽게 계산했습니다. 이후 sorted() 함수와 lambda 키를 조합해 두 번의 정렬을 수행하는 것이 핵심입니다. 첫 번째 정렬로 글자를 알파벳 순으로 정리한 뒤, 두 번째 정렬에서 빈도수를 기준으로 내림차순 정렬하면 안정 정렬(stable sort) 특성 덕분에 동일 빈도수 글자들의 알파벳 순서가 자연스럽게 유지됩니다.
입력
"TUTORIALSPOINT"
출력
[[3, 'T'], [2, 'I'], [2, 'O']]
마무리
이처럼 Counter와 sorted 함수를 조합하면 복잡한 반복문 없이도 문자열 빈도 분석 문제를 간결하고 효율적으로 해결할 수 있습니다. 시간 복잡도는 문자열 길이를 n이라 할 때 O(n log n)으로, 대부분의 실무 상황에서 충분히 빠른 성능을 제공합니다.