-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
index 와 max, min 함수로 풀어도 시간상 상관없는 걸까요?
24.04.07 15:17 작성 조회수 47
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