[백준 2750] 수 정렬하기.py

2750번: 수 정렬하기

백준 12단계 문제

난이도

브론즈 1

유형

구현, 정렬 알고리즘을 사용한다.

접근

입력받는 수의 개수 N의 범위가 1에서부터 1000까지이므로 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있다.
수들을 차례로 비교하는 방법과 파이썬 내장 함수 sort를 이용하는 방법 2가지로 풀어보자.

풀이 1

정렬되지 않은 수들을 입력받아 리스트 a에 저장한다.
정렬된 수를 저장할 빈 리스트 b도 미리 만들어준다.

가장 작은 수를 리스트 a의 첫 원소인 a[0]라고 가정하고 차례로 원소들을 비교해본다.
min보다 작은 원소를 찾았을시에는 그 수를 min값으로 갱신한다.
리스트 안의 수를 모두 비교했다면 가장 작은 수 min을 리스트 b에 저장하고 그 수를 리스트a에서 제거한다.
이 과정을 a에 아무 원소가 남지 않을때까지 반복한다면 오름차순으로 정렬된 리스트 b를 구할 수 있다.

아래와 같은 방법은 시간복잡도가 꽤나 높은 방법이라고 할 수 있다.
입력 받는 수의 개수가 적어서 망정이지, 범위가 조금만 늘어도 시간 초과가 발생할 수 있다.
그럴땐 시간복잡도가 적은 풀이 2의 방법을 이용해보자.

코드 1

n = int(input())
a = [] # 입력받은 수 저장
b = [] # 정렬된 수 저장

for _ in range(n): a.append(int(input()))
while len(a) > 0:
    min = a[0]
    for i in range(len(a)):
        if min > a[i]: min = a[i]
    b.append(min)
    a.remove(min)

for k in b: print(k)

풀이 2 - sort() 이용

파이썬 내장 함수 sort는 리스트안의 원소들을 오름차순으로 정렬해주는 함수이다.
내부적으로는 퀵 정렬 알고리즘을 사용하고 있어서 삽입 정렬보다는 속도가 빠른 편이다.

원소들을 모두 입력받아 리스트 a에 저장하고 sort 함수를 이용해 오름차순으로 정렬한 후 하나씩 출력해주자.

코드 2

n = int(input())
a = []
for _ in range(n): a.append(int(input()))
a.sort()
for k in a: print(k)