백준 2750번 풀이

문제

주어진 수를 오름차순으로 정렬하기(2751번도 같은 문제인데 버블/선택/삽입으로는 시간초과 뜬다)

풀이

정렬 알고리즘과 관련된 이론적인 설명은 아래를 참고할 것.

정렬 알고리즘

위 글에서 다섯가지 대표적인 정렬 알고리즘을 봤는데, 문제가 하나 있었다. ‘버블 알고리즘은 배열의 길이가 커질수록 시간복잡도가 무지막지하게 증가한다’는 것. 근데 시간제한이 1초여… 그래서 선택 알고리즘으로 했다. 

import sys
N = int(sys.stdin.readline())
array = []

for i in range(N):
    i = int(sys.stdin.readline())
    array.append(i)

입력은 들어오는 만큼 받아서 리스트에 넣으면 된다.

import sys
N = int(sys.stdin.readline())
array_in = []

for i in range(N):
    i = int(sys.stdin.readline())
    array_in.append(i)

def selection_sort(array):
	n = len(array)
	for i in range(n):
		min_index = i
		for j in range(i + 1, n):
			if array[j] < array[min_index]:
				min_index = j
		array[i], array[min_index] =  array[min_index], array[i]
	return array

array_out = selection_sort(array_in)

for i in array_out:
    print(i)

선택 정렬을 함수로 정의하고 돌려서 출력을 하면 되는’데’… 출력이 한줄에 하나씩 나와야 하잖음? 그래서 배열을 통으로 출력하면 안되고 for문으로 출력해야 한다.

2751번도 같은 문제인데, 버블/선택/삽입 정렬로 하면 시간초과 뜬다. 병합이나 퀵을 쓰자.