정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리

들어가며

코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.

---

1. 기본 정렬

Python 정렬

같은 리스트를 제자리에서 정렬(sort)할지, 새 리스트를 받을지(sorted)는 원본을 유지해야 하는지에 따라 고르시면 됩니다.

# 오름차순
arr = [5, 2, 8, 1, 9]
arr.sort()
print(arr)  # [1, 2, 5, 8, 9]

# 내림차순
arr.sort(reverse=True)
print(arr)  # [9, 8, 5, 2, 1]

# 새 리스트 반환
arr = [5, 2, 8, 1, 9]
sorted_arr = sorted(arr)
print(arr)  # [5, 2, 8, 1, 9] (원본 유지)
print(sorted_arr)  # [1, 2, 5, 8, 9]

시간 복잡도

• sort(), sorted(): O(n log n) (Timsort)
• 안정 정렬 보장

---

2. 커스텀 정렬

key 함수

# 절댓값 기준 정렬
arr = [-5, -2, 1, 3, -8]
arr.sort(key=abs)
print(arr)  # [1, -2, 3, -5, -8]

# 문자열 길이 기준
words = ["apple", "pie", "banana"]
words.sort(key=len)
print(words)  # ["pie", "apple", "banana"]

# 튜플 정렬 (첫 번째 요소 기준)
students = [(85, "Alice"), (90, "Bob"), (80, "Charlie")]
students.sort()
print(students)
# [(80, 'Charlie'), (85, 'Alice'), (90, 'Bob')]

다중 조건 정렬

# 점수 내림차순, 이름 오름차순
students = [
    ("Alice", 85),
    ("Bob", 90),
    ("Charlie", 85),
    ("David", 90)
]

students.sort(key=lambda x: (-x[1], x[0]))
print(students)
# [('Bob', 90), ('David', 90), ('Alice', 85), ('Charlie', 85)]

# 나이 오름차순, 이름 내림차순
people = [
    ("Alice", 30),
    ("Bob", 25),
    ("Charlie", 30),
]
people.sort(key=lambda x: (x[1], -ord(x[0][0])))

cmp_to_key

from functools import cmp_to_key

def compare(x, y):
    if x > y:
        return 1
    elif x < y:
        return -1
    else:
        return 0

arr = [5, 2, 8, 1]
arr.sort(key=cmp_to_key(compare))
print(arr)  # [1, 2, 5, 8]

---

3. 실전 문제

문제 1: 가장 큰 수

def largest_number(nums):
    """
    숫자를 이어 붙여 가장 큰 수
    [3, 30, 34, 5, 9] → "9534330"
    """
    from functools import cmp_to_key
    
    def compare(x, y):
        if x + y > y + x:
            return -1
        elif x + y < y + x:
            return 1
        else:
            return 0
    
    nums_str = list(map(str, nums))
    nums_str.sort(key=cmp_to_key(compare))
    
    result = ''.join(nums_str)
    return '0' if result[0] == '0' else result

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

문제 2: H-Index

def h_index(citations):
    """
    h번 이상 인용된 논문이 h편 이상
    [3, 0, 6, 1, 5] → 3
    """
    citations.sort(reverse=True)
    
    h = 0
    for i, citation in enumerate(citations):
        if citation >= i + 1:
            h = i + 1
        else:
            break
    
    return h

print(h_index([3, 0, 6, 1, 5]))  # 3
print(h_index([10, 8, 5, 4, 3]))  # 4

문제 3: 구간 합치기

def merge_intervals(intervals):
    """
    겹치는 구간 합치기
    [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
    """
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        if current[0] <= last[1]:
            merged[-1] = [last[0], max(last[1], current[1])]
        else:
            merged.append(current)
    
    return merged

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))
# [[1, 6], [8, 10], [15, 18]]

문제 4: 회의실 배정

def max_meetings(meetings):
    """
    겹치지 않는 최대 회의 수
    [(1, 4), (3, 5), (0, 6), (5, 7)] → 3
    """
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end = 0
    
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings))  # 4

---

4. 정렬 활용 패턴

패턴 1: 정렬 + 투 포인터

def two_sum_sorted(arr, target):
    """
    정렬 후 투 포인터로 합 찾기
    """
    arr.sort()
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [arr[left], arr[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return None

print(two_sum_sorted([2, 7, 11, 15], 9))  # [2, 7]

패턴 2: 정렬 + 이진 탐색

from bisect import bisect_left

def count_smaller(arr, target):
    """
    정렬 후 이진 탐색
    """
    arr.sort()
    idx = bisect_left(arr, target)
    return idx

arr = [5, 2, 8, 1, 9]
print(count_smaller(arr, 6))  # 3 (1, 2, 5)

패턴 3: 정렬 + 그리디

def assign_cookies(children, cookies):
    """
    아이들에게 쿠키 배정 (최대 만족)
    """
    children.sort()
    cookies.sort()
    
    i = j = 0
    while i < len(children) and j < len(cookies):
        if cookies[j] >= children[i]:
            i += 1
        j += 1
    
    return i

children = [1, 2, 3]
cookies = [1, 1]
print(assign_cookies(children, cookies))  # 1

---

실전 팁

정렬 디버깅

def debug_sort(arr, key=None):
    """정렬 과정 출력"""
    print("원본:", arr)
    sorted_arr = sorted(arr, key=key)
    print("정렬:", sorted_arr)
    return sorted_arr

students = [("Alice", 85), ("Bob", 90), ("Charlie", 80)]
debug_sort(students, key=lambda x: x[1])

정렬 시간 측정

import time

arr = list(range(100000, 0, -1))

start = time.time()
arr.sort()
end = time.time()

print(f"정렬 시간: {(end - start) * 1000:.2f}ms")

---

정리

핵심 요약

1. Python 정렬: sort(), sorted(), key 함수
2. 커스텀 정렬: lambda, cmp_to_key
3. 다중 조건: 튜플 반환 (조건1, 조건2)
4. 활용 패턴: 투 포인터, 이진 탐색, 그리디
5. 시간 복잡도: O(n log n)

추천 문제

백준:

• 1427번: 소트인사이드
• 11650번: 좌표 정렬하기
• 1931번: 회의실 배정

프로그래머스:

• 가장 큰 수
• H-Index

LeetCode:

• 56. Merge Intervals
• 435. Non-overlapping Intervals

다음 단계

• 정렬 기초
• 고급 정렬
• 동적 프로그래밍

---

관련 글

• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• 정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
• 이진 탐색 | O(log n) 탐색 알고리즘 완벽 정리
• DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
• C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선