정렬(3)

파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러리인 sorted()함수를 제공한다.
sorted()는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다. 최악의 경우에도 시간 복잡도 O(N*log(n)) 을 보장한다는 특징이 있다.

sorted() : list, dic 자료형 등을 입력받아서 정렬된 결과를 반환한다.
sort() : 리스트 객체의 내장 함수이며, 별도의 정렬된 리스트를 반환하지 않고 원본이 바로 정렬된다.

또한 sorted()나 sort()를 이용할 때, key 매개변수를 입력으로 줄 수 있다.
key 값으로는 하나의 함수가 들어가야 하며 이는 정렬의 기준이 된다.

key를 활용한 sorted(), sort()

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

def mySort(data) :
    return data[1]

# sorted() : 복사본을 넘겨 result에 정렬된 list 반환
result = sorted(array, key=mySort)
print(result)
print(array)

# sort() : 원본이 바로 정렬됨 , list 객체의 내장된 method
array.sort(key=mySort)
print(array)

---

코딩 테스트에서의 정렬 알고리즘

정렬 라이브러리는 항상 최악의 경우에도 $O(NlogN)$을 보장한다. 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 정렬 알고리즘을 구현하는 것보다 훨씬 효과적이다.
따라서 문제에서 별도의 요구가 없으면 라이브러리를 활용하고, 특수한 경우의 경우 계수 정렬을 사용하자.

---

위에서 아래로

문제 설명 :

문제 풀이 :

n = int(input())

array = []
for i in range(n) :
    array.append(int(input()))

array = sorted(array, reverse=True)

for i in array:
    print(i, end=' ')

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

문제 설명 :

문제 풀이 :

n = int(input())

array = []

for i in range(n) :
    user_input = input().split()
    array.append( (user_input[0], int(user_input[1])) )

# array를 lambda식을 이용하여 정렬
array = sorted(array, key = lambda stduent : stduent[1]) 

for student in array :
    print(student[0], end=' ')

---

두 배열의 원소 교체

문제 설명 :

아이디어 :

• 배열 A를 오름차순 정렬, 배열 B를 내림차순 정렬
• 0번 index부터 k-1 index까지 배열 A의 값과 B의 값을 비교
• 배열 A의 값이 작은 경우에만 배열 B와 교환

문제 풀이 :

n, k = map(int, input().split())
arrA = list(map(int, input().split()))
arrB = list(map(int, input().split()))

arrA.sort()
arrB.sort(reverse=True)

for i in range(k) :
    if(arrA[i] < arrB[i]) :
        arrA[i] = arrB[i]
    else :
        break

print(sum(arrA))