연습 문제

정렬 문제는 "정렬 알고리즘을 직접 짜라"보다 "정렬해 두면 풀리는 문제"인 경우가 훨씬 많습니다. 아래 네 문제는 각각 정렬 후 한 번 훑기, 여러 기준 정렬, 사용자 정의 비교, 병합 과정의 응용을 연습합니다. 먼저 스스로 풀어 본 뒤 풀이를 확인하세요.

문제 1. 회의실 예약 합치기

회의실 예약이 (시작, 끝) 쌍의 목록으로 주어집니다. 시각은 정수이고 순서는 뒤섞여 있습니다. 겹치거나 맞닿은 예약을 하나로 합쳐, 회의실이 실제로 쓰이는 시간대 목록을 시작 시각 순으로 돌려주세요. 예를 들어 [(9, 11), (13, 15), (10, 12), (15, 16)]이면 [[9, 12], [13, 16]]입니다.

접근: 시작 시각으로 정렬하면 겹칠 수 있는 예약은 반드시 바로 앞의 결과와만 겹칩니다. 정렬된 순서로 훑으면서, 현재 예약의 시작이 마지막 결과의 끝 이하이면 끝을 늘리고, 아니면 새 구간을 엽니다. 정렬이 O(n log n), 훑기가 O(n)입니다.

def merge_bookings(bookings):
    result = []
    for start, end in sorted(bookings):
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

print(merge_bookings([(9, 11), (13, 15), (10, 12), (15, 16)]))  # [[9, 12], [13, 16]]

문제 2. 대회 순위표

대회 참가자마다 (이름, 점수, 걸린 시간(초))이 있습니다. 점수가 높은 순, 점수가 같으면 시간이 짧은 순, 그것도 같으면 이름의 사전순으로 순위표를 만드세요.

접근: 튜플 키 하나로 세 기준을 표현합니다. 숫자인 점수는 부호를 뒤집어 내림차순을 만들 수 있습니다. 문자열처럼 부호를 뒤집을 수 없는 기준을 내림차순으로 해야 한다면, 안정 정렬을 여러 번 하되 가장 덜 중요한 기준부터 정렬합니다. Python의 reverse=True도 안정성을 유지합니다.

players = [("lee", 90, 300), ("kim", 95, 410), ("park", 90, 280), ("choi", 90, 300)]

ranked = sorted(players, key=lambda p: (-p[1], p[2], p[0]))
print([p[0] for p in ranked])  # ['kim', 'park', 'choi', 'lee']

# 같은 결과를 안정 정렬 여러 번으로: 덜 중요한 기준부터
step = sorted(players, key=lambda p: p[0])
step = sorted(step, key=lambda p: p[2])
step = sorted(step, key=lambda p: p[1], reverse=True)
print([p[0] for p in step])    # ['kim', 'park', 'choi', 'lee']

문제 3. 이어 붙여 가장 큰 수 만들기

음이 아닌 정수 목록이 주어집니다. 순서를 마음대로 바꿔 이어 붙였을 때 만들 수 있는 가장 큰 수를 문자열로 돌려주세요. [3, 30, 34, 5, 9]이면 "9534330"입니다. 모두 0이면 "0"입니다.

접근: 단순히 큰 수나 사전순으로 정렬하면 3과 30 같은 경우에 틀립니다. 두 문자열 a, b에 대해 a + b와 b + a 중 큰 쪽이 되도록 순서를 정하는 비교 함수를 씁니다. 이 비교는 추이성이 성립하므로 정렬에 쓸 수 있습니다. 결과가 "000"처럼 0으로만 이루어지면 "0"으로 줄입니다.

from functools import cmp_to_key

def largest_number(nums):
    words = [str(n) for n in nums]

    def compare(a, b):
        if a + b > b + a:
            return -1   # a를 앞에
        if a + b < b + a:
            return 1
        return 0

    words.sort(key=cmp_to_key(compare))
    return "".join(words).lstrip("0") or "0"

print(largest_number([3, 30, 34, 5, 9]))  # 9534330
print(largest_number([0, 0]))             # 0

문제 4. 순서가 뒤바뀐 쌍 세기

정수 배열에서 i < j인데 a[i] > a[j]인 쌍(역순 쌍)의 개수를 구하세요. 배열 길이는 최대 20만입니다. 예를 들어 [3, 1, 2]는 (3, 1), (3, 2) 두 쌍입니다.

접근: 모든 쌍을 보면 O(n²)이라 너무 느립니다. 병합 정렬의 합치기 단계에서, 오른쪽 원소 right[j]를 꺼낼 때 왼쪽에 남아 있는 원소 len(left) - i개는 모두 그보다 크고 원래 앞에 있었으므로 역순 쌍입니다. 이 개수를 더해 가면 정렬과 동시에 O(n log n)에 답이 나옵니다.

def count_inversions(a):
    def solve(items):
        if len(items) <= 1:
            return items, 0
        mid = len(items) // 2
        left, x = solve(items[:mid])
        right, y = solve(items[mid:])
        merged, i, j, cross = [], 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                cross += len(left) - i
        merged += left[i:] + right[j:]
        return merged, x + y + cross

    return solve(list(a))[1]

print(count_inversions([3, 1, 2]))        # 2
print(count_inversions([5, 4, 3, 2, 1]))  # 10

같은 값은 역순 쌍이 아니므로 <=일 때 왼쪽을 먼저 꺼내야 합니다. <로 쓰면 같은 값을 잘못 셉니다.

정리

• 구간 문제는 시작점으로 정렬한 뒤 한 번 훑는 패턴이 기본입니다.
• 여러 기준은 튜플 키로, 뒤집기 어려운 기준은 안정 정렬을 여러 번 하는 방식으로 처리합니다.
• 사용자 정의 비교 함수는 일관성(추이성)이 성립할 때만 올바르게 동작합니다.
• 병합 정렬의 합치기 단계는 역순 쌍처럼 "앞뒤 관계를 세는" 문제의 도구가 됩니다.