[Algorithm] 정렬 - Sort (Python)

📌 정렬 알고리즘

이것이 취업을 위한 코딩테스트다에서 제공한 문제를 풀어보았다.

대부분의 프로그래밍 언어에서 제공하는 정렬 라이브러리는 가장 효율적이게 구현되어 있다. 파이썬의 정렬 라이브러리는 병합 정렬에 삽입 정렬의 아이디어를 더한 하이브리드 방식의 알고리즘을 사용하고 있기 때문에 최악의 경우에도 O(N logN)의 시간 복잡도를 갖는다고 한다. 결국, 우리가 직접 퀵 정렬을 구현하는 것보다 더욱 효과적이다. 따라서, 문제에서 특별한 요구를 하는 경우가 아닌 이상 정렬 라이브러리를 최대한 활용하도록 하자.

정렬 알고리즘의 이론은 해당 포스트에 정리해 두었으니, 참고하시길 바란다.

위에서 아래로

정렬 라이브러리는 기본적으로 오름차순의 정렬 알고리즘을 제공한다. 해당 문제에서는 내림차순 정렬을 요구하는데, sorted() 함수의 reverse 매개변수를 잘 활용하면 쉽게 해결할 수 있다.

내가 작성한 코드

n = int(input())

_list = []
for _ in range(n):
	_list.append(int(input()))

_list.sort(reverse=True)

# unpacking
print(*_list)

성적이 낮은 순서로 학생 출력하기

리스트의 원소가 2개 이상의 데이터를 갖고 있을 때, 파이썬의 정렬 라이브러리는 첫번째 데이터를 기준으로 정렬을 한다. 해당 문제에서는 두번째 데이터를 기준으로 정렬할 것을 요구하는데, 이는 key 매개변수를 통해 쉽게 해결할 수 있다. key 매개변수를 갖는 sorted() 함수는 key 값을 기준으로 오름차순으로 정렬한다.

내가 작성한 코드

n = int(input())

_list = []

for _ in range(n):
	a, b = input().split()
	
	_list.append((a, int(b)))

_list.sort(key=lambda x: x[-1])

for i in _list:
	print(i[0], end=" ")

두 배열의 원소 교체

배열 A를 오름차순으로, 배열 B를 내림차순으로 정렬하여 0번 인덱스부터 k-1번 인덱스까지의 값들을 바꾸어주면 된다.

예시 코드

n, k = map(int, input().split())
listA = list(map(int, input().split()))
listB = list(map(int, input().split()))

listA.sort()
listB.sort(reverse=True)

for idx in range(k):
	if listA[idx] < listB[idx]:
		listA[idx], listB[idx] = listB[idx], listA[idx]
	
	# 교체하지 않는 경우
	else:
		break

print(sum(listA))

처음에 간과한 것이 list A의 가장 작은 값이 list B의 가장 큰 값보다 큰 경우가 존재할 수 있다. 그래서 조건문을 통해 해당 조건을 처리해주었다.

국영수

앞서 말했듯이, 2개 이상의 데이터를 원소로 하는 리스트에 정렬 라이브러리를 적용하면 첫번째 데이터를 기준으로 정렬된다. 이 때, key 매개변수를 활용하여 정렬 기준을 정할 수 있고, 2개 이상의 key를 제공한다면 이는 우선순위의 역할을 하게 된다. 그래서 key의 첫번째 원소를 기준으로 정렬하고, 첫번째 원소가 같은 값들이 있으면 해당 데이터는 두번째 원소를 기준으로 정렬한다.

내가 작성한 코드

import sys
input = sys.stdin.readline

n = int(input())

_list = []

for _ in range(n):
	name, kor, eng, math = input().split()
	_list.append((name, int(kor), int(eng), int(math)))

_list.sort(key=lambda x: (-x[1], x[2], -x[3], x[0]))

for item in _list:
	print(item[0])

안테나

해당 문제의 핵심 아이디어는 정렬한 값 중 가장 가운데의 값을 선택하면 최적의 해를 뽑아낼 수 있다는 것이다.

내가 작성한 코드

n = int(input())

house = list(map(int, input().split()))

print(sorted(house)[(n-1) // 2])

실패율

계수 정렬을 활용하여 각 스테이지에 머물러 있는 플레이어들의 수를 배열에 저장했다. 그리고 반복문을 통해 낮은 스테이지부터 차례로 접근하여 현재 스테이지에 머물러 있는 플레이어 수 / 현재 스테이지에 진입한 플레이어를 구해주었고, 전체 플레이어에서 현재 스테이지에 머물러 있는 플레이어를 빼주어 다음 스테이지에 진입한 플레이어 수를 반환했다. 이를 스테이지 넘버와 함께 answer 배열에 넣어 반복문이 끝난 뒤에는 sorted() 함수와 key 매개변수를 활용하여 실패율을 기준으로 정렬해주었다.

내가 작성한 코드

# 계수 정렬
stay = [0] * (n + 1)

for i in range(len(stages)):
	stay[stages[i]-1] += 1

# 전체 플레이어 수
player = len(stages)
answer = []
for idx in range(n):
	if player:
		answer.append((idx, stay[idx] / player))

	# 현재 스테이지에 진입한 플레이어가 0명인 경우
	else:
		answer.append((idx, 0))	
	player -= stay[idx]

# 실패율을 기준으로 정렬
answer.sort(key=lambda x: -x[1])
answer = [i[0] + 1 for i in answer]

print(answer)

--

참고 도서

🙇🏻‍♂️ 나 동빈, 이것이 취업을 위한 코딩테스트다