[2026] 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리
![[2026] 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리](/og/s/algorithm-series-08-sorting-problems.webp)
이 글의 핵심
코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.
들어가며
코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 기본 정렬
Python 정렬
같은 리스트를 제자리에서 정렬(sort)할지, 새 리스트를 받을지(sorted)는 원본을 유지해야 하는지에 따라 고르시면 됩니다.
아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 오름차순
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 함수
다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 절댓값 기준 정렬
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')]다중 조건 정렬
다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 점수 내림차순, 이름 오름차순
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
아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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: 가장 큰 수
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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: 구간 합치기
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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: 회의실 배정
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)) # 44. 정렬 활용 패턴
패턴 1: 정렬 + 투 포인터
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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: 정렬 + 이진 탐색
아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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: 정렬 + 그리디
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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실전 팁
정렬 디버깅
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
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])정렬 시간 측정
아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 코드를 직접 실행해보면서 동작을 확인해보세요.
import time
arr = list(range(100000, 0, -1))
start = time.time()
arr.sort()
end = time.time()
print(f"정렬 시간: {(end - start) * 1000:.2f}ms")정리
핵심 요약
- Python 정렬: sort(), sorted(), key 함수
- 커스텀 정렬: lambda, cmp_to_key
- 다중 조건: 튜플 반환 (조건1, 조건2)
- 활용 패턴: 투 포인터, 이진 탐색, 그리디
- 시간 복잡도: O(n log n)
추천 문제
백준:
- 1427번: 소트인사이드
- 11650번: 좌표 정렬하기
- 1931번: 회의실 배정 프로그래머스:
- 가장 큰 수
- H-Index LeetCode:
- 56. Merge Intervals
- 435. Non-overlapping Intervals