[알고리즘] 정렬(Sorting) (2) 정렬 라이브러리 sorted(), sort()

이것이 취업을 위한 코딩테스트다 with 파이썬

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

6장. 정렬

파이썬의 정렬 라이브러리

- sorted() 함수 : 기본 정렬 라이브러리. 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특성이 있다. 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

# 출력
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

- sort() 함수 : 리스트 객체의 내장 함수. 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

array.sort()
print(array)

# 출력
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

- key 매개변수를 입력받을 수 있다. key 값으로는 하나의 함수가 들어가야하며 이는 정렬 기준이 된다.

예제) 정렬 라이브러리에서 key를 활용한 소스코드

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
	return data[1]

result = sorted(array, key=setting)
print(result)

# 출력
# [('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 라이브러리의 시간 복잡도

- 항상 최악의 경우에도 O(NlogN)을 보장한다

 

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

실전 문제 2. 위에서 아래로

- 모든 수는 1이상 100,000이하이므로 어떠한 정렬 알고리즘을 사용해도 문제 해결 가능하다

- 가장 코드가 간결해지는 파이썬의 기본 정렬 라이브러리 이용하는 것이 효과적이다

# N을 입력받기
n = int(input())

# N개의 정수를 입력받아 리스트에 저장
arr = []
for i in range(n):
    arr.append(int(input()))

# 파이썬 기본 정렬 라이브러리를 이용하여 정렬 수행
arr = sorted(arr, reverse=True)
# arr.sort(reverse=True)

# 정렬이 수행된 결과를 출력
for i in arr:
    print(i, end=" ")

실전 문제 3. 성적이 낮은 순서로 학생 출력하기

- 학생정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 한다

- 튜플 문법 참고

# N을 입력받기
n = int(input())

# N명의 정보를 입력받아 리스트에 저장
student = []
for i in range(n):
    input_data = input().split()
    # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
    student.append((input_data[0], int(input_data[1])))

# 키를 이용하여, 점수를 기준으로 정렬
student = sorted(student, key=lambda student : student[1])

# 정렬이 수행된 결과를 출력
for i in student:
    print(i[0], end=' ')

실전 문제 4. 두 배열의 원소 교체

- 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 한다. 단 배열 A에서 가장 작은 원소가 B에서 가장 큰 원소보다 작을 때만 교체를 수행해야 한다. 이러한 과정을 K번 반복한다

- 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.

n, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()                # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True)    # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
        # 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else:   # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        break

print(sum(a)) # 배열 A의 모든 원소의 합을 출력