(이코테 w/ Python) 정렬 알고리즘 문제 풀이

김디니 2022. 7. 2. 22:19

from random import randint
import time

정렬을 수행시킬 목적으로 랜덤한 10000개의 데이터를 이용한다.

파이썬 라이브러리 중 randint 함수를 사용한다.

array = []
for _ in range(10000):

array 함수에 총 100개의 데이터가 랜덤하게 1부터 100 사이의 값으로 담길 수 있도록 한다.

start_time =time.time()
...
end_time = time.time()

수행시간을 측정하기 위해 start time과 end time 변수가 실제 알고리즘 바깥쪽에 서론되어 있다.

(선택 정렬 코드가 이들의 안쪽에 있다.)

선택 정렬을 수행한 결과를 출력하도록 만들려면 끝 시간에서 시작 시간을 뺀 값을 출력하면 된다.

그래서 약 35초의 시간이 소요되는 것을 확인할 수 있다.

(*오른쪽 코드)

1부터 100사이의 데이터가 array에 담길 수 있도록 한다.

수행 시간을 측정할 때 파이썬에서 기본적으로 제공하는 표준 정렬 라이브러리를(array.sort)를 사용한다.

파이썬의 경우 병합 정렬을 기반한 하이브리드 식의 정렬 알고리즘을 사용하기 때문에 최악의 경우 O(NloN)의 시간 복잡도를 보장한다.

실제 수행 결과를 확인해보면 선택 정렬과 비교했을 때 1초보다 짧은, 상대적으로 짧은 시간에 정렬을 수행하는 것을 확인할 수 있다.

문제 해결 아이디어

매번 배열 A에서 가장 작은 원소를 골라서 배열 B에서 가장 큰 원소와 교체한다.

가장 먼저 배열 A와 B가 주어지면 A에 대하여 오름차순으로 정렬하고 B에 대하여 내림차순으로 정렬한다.

이후 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때만 교체를 수행한다.

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

코드 예시

n, k = map(...)
a = list(...)
b = list(...)

n과 k를 입력 받는다.

배열 a와 b에 대해서 모두 입력 받는다.

a.sort()

배열 a는 오름차순으로 정렬을 수행하고

b.sort(reverse=True)

배열 b는 내림차순으로 정렬을 수행한다.

정렬 함수를 호출할 때 reverse 속성의 값으로 true 값을 넣어주게 되면 정렬을 수행할 때 내림차순으로 수행한다.

for i in range(k):

첫 번째 인덱스부터 차례대로 인덱스를 확인하며 두 배열의 원소를 최대 K번 비교한다.

if a a[i] < b[i]:
    a[i], b[i] = b[i], a[i]

매번 a의 원소가 b 원소보다 작을 때 두 원소를 교체해서 배열 a의 모든 원소의 합이 더 커지도록 만든다.

그렇지 않고 a의 원소가 b의 원소보다 크거나 같을 때 더이상 배열 a의 원소의 합을 크게 만들 수 없기 때문에 이러한 경우에는 반복문을 탈출할 수 있도록 한다.

그리하여 배열 A의 모든 원소의 합을 출력하도록 한다.