3. 정렬 활용

정렬은 그 자체가 목적이기보다 거의 모든 문제의 전처리입니다. 어질러진 책상에서는 뭘 찾기 힘들지만, 이름순으로 정리해두면 원하는 걸 금방 집어들 수 있죠. 알고리즘도 똑같습니다. 투 포인터·이진 탐색·그리디가 전부 "정렬된 상태"를 전제로 하죠. 그래서 정렬 알고리즘을 직접 짜는 것보다, 파이썬이 제공하는 sorted와 key를 자유자재로 쓰는 게 훨씬 중요합니다.

이 한 챕터에서 배우는 것:

• sorted(새 리스트)와 .sort()(제자리 정렬)의 차이
• key로 정렬 기준을 마음대로 바꾸는 법
• 튜플을 이용한 여러 기준 정렬과 reverse
• 정렬이 왜 투 포인터·이진 탐색·그리디의 밑밥이 되는지

sorted vs .sort(), 뭐가 다를까?

둘 다 정렬하지만 결과를 어디에 두느냐가 다릅니다.

• sorted(리스트): 원본은 그대로 두고 정렬된 새 리스트를 반환합니다.
• 리스트.sort(): 원본 리스트 자체를 정렬하고 None을 반환합니다. (반환값 없음!)

nums = [3, 1, 2]

new = sorted(nums)   # 새 리스트를 만듦
print(new)           # [1, 2, 3]
print(nums)          # [3, 1, 2]  (원본은 그대로!)

nums.sort()          # 원본 자체를 바꿈
print(nums)          # [1, 2, 3]

💡 nums = nums.sort() 는 초보자가 가장 많이 하는 실수입니다. .sort()는 None을 반환하므로 nums가 None이 되어버려요. 제자리 정렬은 nums.sort()처럼 대입 없이 호출해야 합니다.

sorted는 리스트뿐 아니라 어떤 순회 가능한 것이든 받아서 리스트로 돌려줍니다. 문자열이나 튜플, 집합도 됩니다.

print(sorted("dcba"))        # ['a', 'b', 'c', 'd']
print(sorted((3, 1, 2)))     # [1, 2, 3]
print(sorted({5, 3, 9}))     # [3, 5, 9]

정렬은 내부적으로 원소들을 비교하며 자리를 잡는데, 파이썬의 정렬은 O(n log n) 입니다. n이 100만이면 약 2천만 번 정도라 1초 안에 거뜬합니다. 우리가 직접 이중 반복문으로 짜면 O(n²)이라 100만이면 1조 번, 절대 못 끝냅니다. 정렬은 웬만하면 직접 짜지 말고 sorted를 쓰세요.

reverse로 내림차순 정렬

기본은 오름차순(작은 것부터)입니다. reverse=True를 주면 내림차순이 됩니다.

nums = [3, 1, 2]

print(sorted(nums, reverse=True))   # [3, 2, 1]

nums.sort(reverse=True)             # 제자리 버전도 똑같이
print(nums)                         # [3, 2, 1]

key로 정렬 기준 바꾸기

여기서부터가 진짜입니다. key에 함수를 주면, "각 원소를 무엇으로 보고 비교할지"를 바꿀 수 있어요. 원소를 그대로 비교하는 게 아니라 key(원소)의 결과로 비교합니다.

예를 들어 단어들을 길이순으로 정렬해봅시다.

words = ["banana", "kiwi", "apple", "fig"]

print(sorted(words, key=len))
# ['fig', 'kiwi', 'apple', 'banana']   (길이 3, 4, 5, 6 순)

key=len은 각 단어를 len(단어), 즉 길이로 바꿔서 비교하라는 뜻입니다. key를 안 주면 사전순(알파벳순)으로 정렬됐겠죠.

key에는 lambda(이름 없는 짧은 함수)를 자주 씁니다. 절댓값 기준으로 정렬하는 예시입니다.

nums = [-5, 3, -1, 4, -2]

print(sorted(nums, key=lambda x: abs(x)))
# [-1, -2, 3, 4, -5]   (절댓값 1, 2, 3, 4, 5 순)

lambda x: abs(x)는 "원소 x를 받아서 abs(x)를 돌려주는 함수"입니다. 그 반환값으로 순서를 정하는 거죠.

💡 key가 주는 값은 비교에만 쓰이고, 실제로 리스트에 담기는 건 원래 원소입니다. 위에서 절댓값으로 순서를 정했지만 결과에는 -1, -2 같은 원래 값이 그대로 들어있죠.

튜플로 여러 기준 정렬하기

"먼저 A 기준으로, 같으면 B 기준으로" 같은 다중 정렬은 실전에서 정말 자주 나옵니다. 학생을 점수 높은 순으로, 점수가 같으면 이름 사전순으로 세우는 상황을 떠올려보세요.

비결은 key가 튜플을 반환하게 하는 것입니다. 파이썬은 튜플을 비교할 때 앞 원소부터 차례로 비교합니다. 첫 번째가 같으면 두 번째로 넘어가죠.

students = [
    ("Alice", 90),
    ("Bob", 85),
    ("Charlie", 90),
    ("Dave", 85),
]

# 점수 내림차순, 점수가 같으면 이름 오름차순
result = sorted(students, key=lambda s: (-s[1], s[0]))
for name, score in result:
    print(name, score)
# Alice 90
# Charlie 90
# Bob 85
# Dave 85

여기서 핵심 트릭이 하나 있습니다. 점수는 내림차순, 이름은 오름차순이라 방향이 서로 다릅니다. reverse=True는 튜플 전체에 걸리기 때문에 쓸 수 없어요. 대신 점수에 -(마이너스)를 붙여 -s[1]로 만들면, 큰 점수가 작은 값이 되어 오름차순 정렬만으로 "점수는 내림, 이름은 오름"이 동시에 됩니다.

💡 숫자는 -값으로 방향을 뒤집을 수 있지만, 문자열엔 마이너스를 못 붙입니다. 문자열까지 방향을 섞어야 하면 정렬을 두 번 나눠서 하는 등 다른 방법을 써야 해요. 다행히 대부분의 문제는 "숫자 하나만 내림차순"이라 이 마이너스 트릭으로 해결됩니다.

참고로 파이썬 정렬은 안정 정렬(stable sort) 입니다. 같은 key 값을 가진 원소들끼리는 원래 순서가 유지돼요. 이 성질을 이용하면 정렬을 여러 번 나눠서도 다중 정렬을 만들 수 있습니다.

정렬이 왜 다른 기법의 밑밥일까?

정렬은 그 자체로 답인 경우도 있지만, 진짜 위력은 정렬해두면 다음 단계가 확 쉬워진다는 데 있습니다. 대표적인 세 가지를 볼게요.

이진 탐색의 전제 조건

소수 챕터에서 완전탐색은 O(n)이라고 했죠. 그런데 데이터가 정렬돼 있으면 "가운데를 보고 절반씩 버리는" 이진 탐색으로 O(log n) 만에 찾을 수 있습니다. 파이썬 bisect 모듈이 이걸 해줍니다.

import bisect

nums = [1, 3, 5, 7, 9, 11]   # 반드시 정렬돼 있어야 함!

# 7이 들어갈 위치(= 7보다 작은 원소의 개수)
print(bisect.bisect_left(nums, 7))   # 3

# "5 이상 9 이하인 원소가 몇 개?" 도 순식간에
left = bisect.bisect_left(nums, 5)
right = bisect.bisect_right(nums, 9)
print(right - left)                  # 3   (5, 7, 9)

이진 탐색은 정렬이 안 돼 있으면 절대 못 씁니다. 그래서 "정렬 → 이진 탐색"이 한 세트로 다닙니다.

투 포인터의 밑밥

정렬된 배열에서 "두 수의 합이 특정 값이 되는 쌍 찾기" 같은 문제는, 양 끝에서 포인터 두 개를 좁혀오는 투 포인터로 O(n)에 풉니다. 합이 크면 오른쪽을 당기고, 작으면 왼쪽을 밀죠. 이게 성립하는 이유가 바로 정렬돼 있어서 "지금 합이 크다/작다"로 다음 방향을 정할 수 있기 때문입니다.

def two_sum_sorted(nums, target):
    nums = sorted(nums)          # 먼저 정렬 (이게 전처리!)
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (nums[lo], nums[hi])
        elif s < target:         # 합이 작으면 왼쪽을 키운다
            lo += 1
        else:                    # 합이 크면 오른쪽을 줄인다
            hi -= 1
    return None

print(two_sum_sorted([8, 2, 5, 1, 7], 9))   # (1, 8)

그리디의 밑밥

그리디(매 순간 가장 좋아 보이는 걸 고르는 전략)도 정렬로 시작하는 경우가 많습니다. "회의를 최대한 많이 잡으려면?" 같은 문제는 끝나는 시간이 이른 순으로 정렬해두고 앞에서부터 욕심껏 고르면 최적이 됩니다.

# (시작, 끝) 회의들. 겹치지 않게 최대 몇 개?
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (5, 9), (8, 9)]

meetings.sort(key=lambda m: m[1])   # 끝나는 시간 오름차순 정렬

count = 0
end = 0
for start, finish in meetings:
    if start >= end:      # 이전 회의가 끝난 뒤에 시작 가능하면
        count += 1
        end = finish      # 선택하고, 종료 시간 갱신
print(count)              # 3   ((1,4) → (5,7) → (8,9) 선택)

정렬 한 줄이 없으면 이 그리디는 성립하지 않습니다. "어떤 기준으로 정렬하느냐"가 그리디 문제의 핵심인 경우가 대부분이에요.

💡 문제를 만났을 때 "일단 정렬하면 뭐가 보이지?"를 습관처럼 떠올려보세요. 정렬은 공짜에 가깝고(O(n log n)), 정렬된 순간 이진 탐색·투 포인터·그리디로 가는 길이 열립니다.

정리

💡 정렬 알고리즘 자체(버블·퀵·병합 정렬 등)를 외워서 직접 구현할 일은 코딩테스트에서 거의 없습니다. sorted와 key를 손에 익히는 게 100배 실용적이에요.

직접 풀어보기

1. 단어 리스트 ["pear", "fig", "apple", "kiwi"]를 길이 오름차순, 길이가 같으면 사전순으로 정렬해보세요. (힌트: key=lambda w: (len(w), w))
2. [(이름, 나이)] 튜플 리스트를 나이 내림차순, 나이가 같으면 이름 오름차순으로 정렬해보세요. (힌트: 나이에 마이너스)
3. 정렬된 리스트 [2, 4, 6, 8, 10]에서 bisect를 이용해 6 이상인 원소의 개수를 구해보세요. (정답: 3개)