[Python] 해시와 다중 조건 정렬: 플레이리스트 순서 정리하기

코딩 테스트에서 빈번하게 등장하는 '데이터 집계'와 '정렬 조건 최적화' 문제를 다뤄보았습니다. 단순한 빈도수 계산을 넘어, 동일 빈도 시 등장 순서(우선순위)를 보장해야 하는 엣지 케이스를 해결하는 것이 핵심입니다.

1. 문제 분석

여러 개의 플레이리스트 배열이 주어질 때, 다음 규칙에 따라 음악을 정렬하여 하나의 문자열로 반환해야 합니다.
1. 1순위: 가장 많이 등장한 음악부터 정렬 (빈도수 내림차순)
2. 2순위: 빈도수가 같을 경우, 전체 데이터에서 더 먼저 등장한 음악부터 정렬 (등장 순서 오름차순)

2. 핵심 설계: 절대적 등장 순서(Global Order) 추적

단순히 플레이리스트 배열의 인덱스(enumerate)만으로는 한 문자열 내에 여러 음악이 있을 때의 세부 순서를 보장할 수 없습니다. 따라서 전체 탐색 과정에서 새로운 음악이 발견될 때마다 증가하는 전역 카운터(appearance_order)를 도입하여 해결했습니다.

3. 최종 구현 코드

def solution(playlists):
    freq_map = {}          # 음악별 총 빈도수 저장 (Hash Map)
    first_appearance = {}  # 음악별 최초 등장 절대 순서 저장
    appearance_order = 0   # 전역 순서 카운터
    
    for playlist in playlists:
        songs = playlist.split() # 공백 기준 파싱
        
        for song in songs:
            # 빈도수 업데이트: .get()을 사용하여 초기값 0 보장
            freq_map[song] = freq_map.get(song, 0) + 1
            
            # 최초 등장 시점에만 절대 순서 기록
            if song not in first_appearance:
                first_appearance[song] = appearance_order
                appearance_order += 1
                
    # 정렬 대상 추출
    unique_songs = list(freq_map.keys())
    
    # 다중 조건 정렬 적용
    # -freq_map[x]: 빈도수 기준 내림차순
    # first_appearance[x]: 등장 순서 기준 오름차순
    unique_songs.sort(key=lambda x: (-freq_map[x], first_appearance[x]))
    
    return "".join(unique_songs)

4. 주요 문법 및 기술적 포인트

① dict.get(key, default)의 안전성

딕셔너리에서 존재하지 않는 키를 참조하면 KeyError가 발생합니다. get() 메서드는 키가 없을 경우 두 번째 인자로 전달한 default 값을 반환하므로, + 1 연산을 통해 빈도수를 카운트할 때 별도의 조건문 없이 깔끔하게 처리할 수 있습니다.

② lambda를 활용한 다중 조건 정렬

파이썬의 sort는 튜플을 정렬 키로 반환하면 왼쪽 요소부터 차례대로 비교합니다.

• 내림차순이 필요한 숫자형 데이터에는 -를 붙여 대소 관계를 반전시킵니다.
• (-freq_map[x], first_appearance[x])는 "빈도수는 크면 클수록(마이너스 값이 작을수록) 앞으로, 등장 순서는 작으면 작을수록 앞으로"라는 복합적인 요구사항을 단 한 줄로 해결합니다.

③ 해시 테이블(Dictionary)의 시간 복잡도

음악의 이름을 키로 사용하여 데이터를 관리함으로써, 삽입과 조회 모두 $O(1)$의 시간 복잡도를 가집니다. 전체 음악의 개수가 $N$, 고유 음악의 개수가 $M$일 때, 전체 로직은 대략 $O(N + M \log M)$ 이내에 수행되므로 매우 효율적입니다.

5. 마무리

데이터의 물리적 순서가 논리적 우선순위에 영향을 미치는 경우, 탐색 시점의 상태를 해시 테이블에 박제해두는 테크닉이 유용합니다. enumerate의 한계를 global counter로 극복하는 과정이 이번 구현의 핵심이었습니다.