이것이 취업을 위한 코딩 테스트다 CHAPTER 6 정렬

• 정렬
  • 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• list.reverse()
  • 리스트를 뒤집는 연산
  • O(N)
• 선택정렬
  • 매번 가장 작은 것을 선택하는 알고리즘
  • 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복
  • O(N^2)

# 선택 정렬
arr = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(arr)):
	min_index = i # 가장 작은 원소의 인덱스
    for j in range(i+1,len(arr)):
    	if arr[min_index] > arr[j]:
        	min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
    
print(arr)

• 삽입정렬
  • 특정한 데이터를 적절한 위치에 삽입하는 것
  • 데이터가 거의 정렬되어 있을 때 훨씬 효율적
  • O(N^2)

# 삽입 정렬
arr = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(arr)):
	for j in range(i,0,-1):
    	if arr[j] < arr[j-1]:
        	arr[j], arr[j-1] = arr[j-1], arr[j]
        else:
        	break

• 퀵정렬
  • 기존 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸기
  • 기준 데이터 == 피벗
    • 왼쪽에서부터 피벗보다 큰 데이터 찾고, 오른쪽에서부터 피벗보다 작은 데이터 찾기
    • 양쪽 다 찾으면 교체
    • 만약 두 값이 엇갈린 경우에는 작은데이터와 피벗 교체
  • O(NlogN)
    • 최악의 경우 O(N^2)

# 퀵정렬
a = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr):
	if len(arr) <= 1:
    	return arr
        
    pivot = arr[0]
    tail = arr[1:]
    
    left = [x for x in tail if x <= pivot]
    rigth = [x for x in tail if x > pivot]
    
    return quick_sort(left) + [pivot] + quick_sort(right)
    
print(quick_sort(arr))

• 계수정렬
  • 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
  • 데이터 개수 N, 데이터 중 최댓값 K인 경우 O(N+K)
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용
    • 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 사용X
  • 때에 따라서 심각한 비효율성을 초래

# 계수정렬
arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

count = [0]*(max(arr)+1)
for i in range(len(arr)):
	count[arr[i]] += 1
   
for i in range(len(count)):
	for j in range(count[i]):
    	print(i,end=' ')

 

문제 2. 위에서 아래로

'''

    Chapter 6. 위에서 아래로

    접근법 1

        .sort() 함수를 사용하여 내림차순 정렬

        reverse = True

'''

import sys
input = sys.stdin.readline

# 수열에 속해 있는 수
N = int(input())
num = list(int(input()) for _ in range(N))
# 내림차순 정렬
num.sort(reverse=True)
# 정렬된 결과를 공백으로 구분
print(*num)

 

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

'''

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

    접근법 1

        이름과 성적을 받아 리스트에 넣고 성적순으로 정렬 후 출력

'''

import sys
input = sys.stdin.readline

# 학생 수
N = int(input())
student = []
for _ in range(N):
    # 이름, 성적
    name, score = input().split()
    student.append([name,int(score)])

# 성적이 낮은 순으로 정렬
student.sort(key = lambda x:x[1])

# 학생이름 출력
for i in range(N):
    print(student[i][0],end=' ')

 

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

'''

    Chapter 6. 두 배열의 원소 교체

    접근법 1

        A는 오름차순, B는 내림차순 정렬

        A의 원소가 B의 원소보다 작을 때 교체

'''

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
# 오름차순
A = sorted(list(map(int,input().split())))
# 내림차순
B = sorted(list(map(int,input().split())),reverse=True)

# K번 반복
for i in range(K):
    # A의 원소와 B의 원소를 비교
    if A[i] < B[i]:
        A[i],B[i] = B[i],A[i]
    else:
        break

print(sum(A))