-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
index 와 max, min 함수로 풀어도 시간상 상관없는 걸까요?
24.04.07 15:17 작성 조회수 59
0
l=int(input())
a=list(map(int,input().split()))
m=int(input())
for i in range(m):
#print(a.index(max(a)),a.index(min(a)),max(a),min(a))
a[a.index(max(a))]-=1
a[a.index(min(a))]+=1
print(max(a)-(min(a)) )
이렇게 간단하게 풀었는데 혹시 값이 많아지면 이게 sort보다 시간이 더 오래 걸리게 될까요?
답변을 작성해보세요.
0
인프런 AI 인턴
2024.04.09
안녕하세요, 인프런 AI 인턴입니다.
코딩공부왕님의 질문에 답변드립니다.
네, 값의 양이 많아질 경우 max
, min
, index
함수를 사용하는 것이 sort
를 사용하는 것보다 시간이 더 오래 걸릴 수 있습니다. max
와 min
함수는 리스트 전체를 탐색해야 하므로 각각 O(n)의 시간 복잡도를 가지고, index
함수 또한 전체를 탐색해야 하므로 O(n)의 시간 복잡도를 가집니다. 따라서 이 코드는 한 반복마다 4n의 시간 복잡도(O(n))를 가지게 됩니다.
반면, sort
함수는 대부분의 경우 O(n log n)의 시간 복잡도를 가지므로, 값의 양이 충분히 많아진다면 max
, min
, index
를 반복적으로 사용하는 것보다 sort
를 사용해 정렬하고 필요한 연산을 하는 편이 더 효율적일 수 있습니다. 하지만 단순히 최댓값과 최솟값의 차이만을 구하는 경우에는 값의 양이 적다면 max
, min
, index
를 사용한 현재의 방식이 더 간결하고 이해하기 쉬울 수 있습니다.
따라서 상황에 따라 적합한 방법을 선택하는 것이 중요합니다. 값의 양이 많아질 것으로 예상되면, 시간 복잡도가 더 낮은 알고리즘을 선택하는 것이 좋습니다.
답변 1