5. 정렬

정렬

1. 각 유형별 예제

1.1 기본 정렬 함수

• sorted(리스트) : 정렬된 새 리스트를 반환 (원본 변화 X)

• 리스트.sort() : 리스트 자체를 정렬 (원본 변화 O)

arr = [5, 2, 9, 1]
sorted_arr = sorted(arr) # [1, 2, 5, 9]
arr.sort() # arr = [1, 2, 5, 9]

1.2 역순 정렬 (내림차순)

sorted(arr, reverse = True)
arr.sort(reverse = True)

1.3 key 인자 사용

정렬 기준을 직접 지정할 수 있다. 보통 lambda랑 같이 많이 쓰인다.

words = ['banana', 'apple', 'cherry']

# 길이순으로 정렬
sorted(words, key=lambda x: len(x)) # ['apple', 'banana', 'cherry']

1.4 튜플 정렬 (여러 기준 정렬)

data = [(1, 'a'), (3, 'c'), (2, 'b'), (2, 'a')]

# 1차: 첫번째 원소 오름차순, 2차: 두번쨰 원소 오름차순
sorted(data) 
# [(1, 'a'), (2, 'a'), (2, 'b'), (3, 'c')]


# 1차: 첫번쨰 원소 내림차순, 2차: 두번째 원소 오름차순
sorted(data, key=lambda x: (-x[0], x[1])) 
# [(3, 'c'), (2, 'a'), (2, 'b'), (1, 'a')]

1.5 객체 정렬

class User:
	def __init__(self, name, age):
		self.name = name
		self.age = age

user = [User("Alice", 30), User("Bob", 20)]
sorted(users, key=lambda x: x.age)

---

2. 연습 예제

예제 2.1: 좌표 정렬

x 기준 오름차순, 같으면 y 기준 오름차순

points = [(1, 2), (3, 4), (1, -1), (2, 2)]

print(sorted(points, key=lambda x: (x[0], x[1])))

''' 출력
[(3, 'c'), (2, 'a'), (2, 'b'), (1, 'a')]
'''

예제 2.2: 문자열 길이 정렬

길이가 짧은 순 → 같으면 사전순

words = ["hello", "my", "name", "is", "chatgpt"]

print(sorted(words, key=lambda x: (len(x), x)))

''' 출력
# ['is', 'my', 'name', 'hello', 'chatgpt']
'''

예제 2.3: 숫자의 합으로 정렬

각 숫자의 자리수 합을 기준으로 정렬 123 → 1+2+3=6, 21→3, 9→9, 111→3

numbers = ["123", "21", "9", "111"]

print(sorted(numbers, key=lambda x: sum(map(int, x))))

''' 출력
['21', '111', '123', '9']
'''

예제 2.4: 파일 이름 정렬

숫자 기준으로 정렬 → 파일 이름에서 숫자 추출해서 정렬

files = [("file7", 15), ("file2", 12), ("file10", 8)]

print(sorted(files, key=lambda x: (int(x[0][4:]))))

''' 출력
[('file2', 12), ('file7', 15), ('file10', 8)]
'''

---

3. 실전 문제

문제 3.1 전투 기록 정렬기

📘 문제 설명

아래 형식의 전투 기록이 주어진다. 각 기록은 (병사ID, 전투력, 피해량) 으로 구성된다.

전투력이 높은 순서대로 정렬하되,

• 전투력이 같으면 피해량이 낮은 병사를 우선
• 전투력과 피해량도 같으면 병사ID가 낮은 순서

로 정렬하시오.

📥 입력 형식

• 첫 줄에 기록 개수 N (1 ≤ N ≤ 1000)
• 그 다음 줄부터 N개의 줄에 걸쳐 병사ID 전투력 피해량 (공백 구분 정수)

📤 출력 형식

• 정렬된 병사ID만 순서대로 한 줄에 공백으로 출력

입력 예시 1

5
101 90 10
102 95 20
103 95 15
104 90 5
105 95 15

출력 예시 1

103 105 102 104 101

해설

N = int(input())
records = [tuple(map(int, input().split())) for _ in range(N)]
sorted_records = sorted(records, key=lambda x: (-x[1], x[2], x[0]))

print(' '.join(str(r[0]) for r in sorted_records))

---

문제 3.2 파일 정렬 시스템

📘 문제 설명

여러 개의 파일명이 주어진다. 각 파일명은 "이름_버전" 형식이며, 버전은 항상 숫자로 끝난다.

예: "update_2", "sensor_10", "update_11"

이 파일들을 버전 숫자 기준 오름차순으로 정렬하시오. 단, 같은 버전이면 이름 사전순으로 정렬한다.

📥 입력 형식

• 첫 줄에 정수 N (1 ≤ N ≤ 1000)
• 다음 줄부터 N개의 파일명

📤 출력 형식

• 정렬된 파일명을 한 줄에 하나씩 출력

입력 예시 1

5
update_2
sensor_10
update_11
sensor_2
sensor_1

출력 예시 1

sensor_1
sensor_2
update_2
sensor_10
update_11

해설

N = int(input())
files = [input().strip() for _ in range(N)]

files.sort(key=lambda x: (int(x.split('_')[1]), x.split('_')[0]))

for f in files:
	print(f)

---

문제 3.3 K번째수

📘 문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[ [2, 5, 3], [4, 4, 1], [1, 7, 3] ]	[5, 6, 3]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

해설

def solution(array, commands):
	answer = []

	for command in commands:
		start = command[0] - 1
		end = command[1]
		target = command[2] - 1

		answer.append(sorted(array[start:end])[target])

	return answer

  
  

test_case = (
	([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]], [5, 6, 3]),
)

  

for idx, (array, commands, answer) in enumerate(test_case, 1):
	result = solution(array, commands)

	if result == answer:
		print('OK')

	else:
		print(result)

---

문제 3.4 가장 큰 수

📘 문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
• itertools 사용 불가

입출력 예

numbers	return
[6, 10, 2]	“6210”
[3, 30, 34, 5, 9]	“9534330”

해설

from functools import cmp_to_key

def compare(a, b):
	if a + b > b + a:
		return -1 # a가 앞

	elif a + b < b + a:
		return 1 # b가 앞

	else:
		return 0
		

def solution(numbers):
	numbers = list(map(str, numbers))
	numbers.sort(key=cmp_to_key(compare))
	result = ''.join(numbers)
	return str(int(result)) # "000" 같은 경우 대비
  

test_case = (
	([6, 10, 2], "6210"),
	([3, 30, 34, 5, 9], "9534330"),
	([9283, 9099, 90, 9], "99283909990")
)


for idx, (numbers, answer) in enumerate(test_case, 1):
	result = solution(numbers)

	if result == answer:
		print('OK')

	else:
		print(result)

디버깅

예시: a = "9", b = "90"

• "9" + "90" → "990"

• "90" + "9" → "909"

• 결과적으로 "990" > "909" → "9"가 "90"보다 앞에 와야 하므로 compare("9", "90") → -1

즉, a + b가 b + a보다 크면 → a를 앞에 두는 정렬 기준을 만듦

예시: [3, 30, 34, 5, 9]

1. 문자열로 변환: ['3', '30', '34', '5', '9']

2. 정렬 기준:

   • "9" + "5" vs "5" + "9" → "95" vs "59" → "9"이 앞

   • "5" + "34" vs "34" + "5" → "534" vs "345" → "5"가 앞

   • 이런 식으로 모든 쌍 비교해서 순서 결정

3. 정렬 결과: ['9', '5', '34', '3', '30']

4. 붙이면 "9534330"

cmp_to_key 역할

a, b 두 값을 직접 비교하는 compare 함수를, key 함수처럼 동작하는 wrapper 객체로 감싸줌

문자열 끼리의 대수 비교는 사전순 으로 판단된다. 이 문제에서는 붙였을 때 더 큰 수 판단과 일치한다.

문자열끼리 비교

‘abc’ > ‘ab’ : True

• 첫번째 문자부터 차례로 비교
• 동일하면 다음문자 비교
• 더 길거나 큰 문자가 먼저 등장하면 그쪽이 더 크다고 판단

“990” > “909” → True

from functools import cmp_to_key

def compare(a, b):
    print(f"비교: {a} vs {b}")
    return -1 if a < b else 1 if a > b else 0

arr = [5, 2, 9]
arr.sort(key=cmp_to_key(compare))
print(arr)

''' 출력
비교: 2 vs 5
비교: 9 vs 2
비교: 9 vs 5
[2, 5, 9]
'''

compare(a, b) 결과	의미	누가 앞으로?
-1	a < b	a가 앞에
1	a > b	a가 뒤에
0	같다	그대로 둬라

정리

개념	설명
compare(a, b)	두 값의 우선순위를 정하는 함수
cmp_to_key(compare)	compare를 key처럼 쓸 수 있게 래핑
sorted(..., key=cmp_to_key(compare))	정렬 과정에서 compare 기준으로 정렬 가능