[알고리즘] 정렬 - (5) 파이썬 정렬 라이브러리 및 실전 문제

5. 파이썬 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.

sorted() 함수는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.

병합 정렬은 일반적으로 퀵 정렬보다 느리지만, 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.

이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.

물론 집합이나 딕셔너리 자료형을 입력받아도 return 값은 리스트이다.

1) sorted.py

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]

2) sort.py

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다.

sort() 함수를 사용하면 된다.

이를 이용하면 별도의 정렬된 리스트가 반환되지않고, 내부 원소가 바로 정렬된다.

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

array.sort()
print(result)

- 출력

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

3) key.py

또한 sorted()나 sort() 를 이용할 때 key 매개변수를 입력으로 받을 수 있다.

key 값으로는 하나의 함수가 들어가야 하며, 이는 정렬 기준이 된다.

혹은 람다(lambda) 함수를 사용할 수도 있다.

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

def setting(data):
    return data[1]

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

- 출력

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

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

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

**[코테에서 정렬 알고리즘이 사용되는 경우]

(1) 정렬 라이브러리로 풀 수 있는 문제

: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.

(2) 정렬 알고리즘의 원리에 대해서 물어보는 문제

: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.

(3) 더 빠른 정렬이 필요한 문제

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

---

🔒 문제1 : 위에서 아래로

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다.

이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다.

수열을 내림차순으로 정렬하는 프로그램을 만드시오.

⌨ 입력

- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 <= N <= 500)

- 둘째 줄부터 N + 1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1이상 100,000 이하의 자연수이다.

🖨 출력

- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.

📚 예제

EX)

- 입력 예시

3
15
27
12

- 출력 예시

27 15 12

📌 풀이

이 문제는 가장 기본적인 정렬을 할 수 있는지 묻는 문제였다.

입력 조건을 보면 수의 개수가 500개 이하로 매우 적고, 모든 수는 1 이상 100,000이하이므로 어떤 정렬 알고리즘을 사용해도 문제가 해결 가능하다.

🔑 python 코드

- 내 코드

# 위에서 아래로
import sys
input = sys.stdin.readline
N = int(input())
arr = [int(input()) for _ in range(N)]

arr.sort(reverse=True)
for i in arr:
    print(i, end = ' ')

- 답안 코드

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

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

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

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

---

🔒 문제2 : 성적이 낮은 순서로 학생 출력하기

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다.

각 학생의 이름과 성적 정보가 주어졌을 때, 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

⌨ 입력

- 첫 번쨰 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)

- 두 번쨰 줄부터 N + 1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

🖨 출력

- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

📚 예제

Ex)

- 입력 예시

2
홍길동 95
이순신 77

- 출력 예시

이순신 홍길동

📌 풀이

이 문제는 학생의 정보가 최대 100,000개 까지 입력될 수 있다. 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다.

그리고 학생의 이름과 점수가 함께 입력되지만, 출력은 이름만되기 때문에 학생 정보를 (점수, 이름)으로 묶은 뒤 점수를 기준으로 정렬해주면 된다.

그래서 파이썬 기본 정렬 알고리즘과 lambda를 사용해서 정렬하면 된다.

🔑 python 코드

- 내 코드

# 성적이 낮은 순서로 학생 출력하기
import sys
input = sys.stdin.readline
N = int(input())
array = []
for i in range(N):
    temp = input().split()
    array.append([temp[0], int(temp[1])])

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

for i in range(N):
    print(array[i][0], end = ' ')

- 답안 코드

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

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

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

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

---

🔒 문제3 : 두 배열의 원소 교체

수현이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.

수현이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.

동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 수현이를 도와야 한다.

N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성해라.

예를 들어 N = 5, K = 3이고 배열 A와 B가 다음과 같다고 하자.

- 배열 A = [1, 2, 5, 4, 3]
- 배열 B = [5, 5, 6, 6, 5]

이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다.

- 연산1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
- 연산2) 배열 A의 원소 '2'와 배열 B의 원소 '6'을 바꾸기
- 연산3) 배열 A의 원소 '3'과 배열 B의 원소 '5'를 바꾸기

세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다.

- 배열 A = [6, 6, 5, 4, 5]
- 배열 B = [3, 5, 1, 2, 5]

이때 배열 A의 모든 원소의 합은 26이 되며, 이보다 더 합을 크게 만들 수는 없다. 따라서 이 예시의 정답은 26이 된다.

⌨ 입력

- 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. ( 1 <= N <= 100,000, 0 <= K <= N )

- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.

- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000 보다 작은 자연수이다.

🖨 출력

- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

📚 예제

Ex)

- 입력 예시

5 3
1 2 5 4 3
5 5 6 6 5

- 출력 예시

26

📌 풀이

이 문제를 해결하기 위한 풀이 방법은 A의 가장 작은 원소와 B의 가장 큰 원소의 크기를 비교하고 둘을 교체하는 것이다.

그래서 배열 A는 오름차순으로, 배열 B는 내림차순으로 정렬한 뒤, A의 가장 작은 원소와 B의 가장 큰 원소를 비교해가며 교체한다.

만약 교체를 K번 했거나, A의 가장 작은 원소가 B의 가장 큰 원소보다 크거나 같아지면 비교를 종료하고 A의 총 합을 출력한다.

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

🔑 python 코드

- 내 코드

# 두 배열의 원소 교체
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort(reverse=True)
j = 0
for i in range(N):
    if (K == 0):
        break
    if(A[i] < B[j]):
        A[i], B[j] = B[j], A[i]
        j += 1
        K -= 1
    else: # 뒤에 더 해봐도 B 배열에 A 배열의 원소보다 큰 값이 없음
        break
print(sum(A))

- 답안 코드

n, k = map(int, input().split()) # N과 K 입력받기
a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기
b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기

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))