단계별로 풀어보기 백준_10818번

최소, 최대

문제는 다음과 같습니다.

 

 

N개의 정수가 첫째 줄에 주어집니다. 

이후 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어집니다.

 

이때 주의 해야 할 점은 N의 범위가 (1<=N<=1,000,000) 입니다.

시간 복잡도가 초과 될 거 같습니다. 따라서 처음에는 최대, 최소 max() , min() 사용하지 말고 보다 빠른 최대, 최소 탐색이 있는지 확인할 것 입니다. 하지만 정렬의 첫 인덱싱, 마지막 인덱싱 또한 정렬을 해야 하므로 O(NlogN)이 소요됩니다.

 

따라서 가장 최적의 시간은 max()와 min()을 바로 구하는 것 입니다.

왜냐하면 o(N)이 여러번 소요 되어서 매우 비효울적인 코드처럼 보이지만 사실 O(N) + O(N) 은 O(N)과 같습니다.

물론 N이 inf 하다는 개념에서 이지만, 일반적으로 O(N)과 같다고 표용되고 있습니다.

 

N = int(input())
L1 = list(map(int,input().split()))
print(min(L1),max(L1))

시간복잡도: O(N)

 

 

다른 사람의 공개된 오답 코드 중 시간초과로 인한 오답 코드를 확인해보겠습니다.

 

드에서 max()와 min()을 반복문 안에서 매번 호출하고 있습니다.
이는 매 반복마다 리스트 전체를 탐색하므로, 시간 복잡도가 O(N²) 이 됩니다.

 

 

따라서 시간초과가 발생한 것 입니다. 이 문제는 최대 O(N)까지 허용하는 문제입니다.

min(), max()유도한 문제입니다.