백준 2750 파이썬 (+시간 복잡도 활용)

백준 2750 : 수 정렬하기

문제

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

백준 2750

 

답안 코드 :

n = int(input())

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

L.sort()
for i in range(len(L)):
    print(L[i])

 

 

생각 :

시간 복잡도 활용하기

시간 제한이 1초이므로 이 조건을 만족하려면 2,000만 번 이하의 연산 횟수로 문제를 해결해야 한다.

(시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 한다.)

 

연산 횟수 계산 방법

ㄴ 연산 횐수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출한다.

 

이 문제는 예를 들어 

버블 정렬 = (1,000,000)^2 > 20,000,000                                     따라서 부적합.

병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000               적합 알고리즘.

 

기본) 시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.