index 와 max, min 함수로 풀어도 시간상 상관없는 걸까요?
223
작성한 질문수 4
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보다 시간이 더 오래 걸리게 될까요?
답변 1
0
안녕하세요, 인프런 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를 사용한 현재의 방식이 더 간결하고 이해하기 쉬울 수 있습니다.
따라서 상황에 따라 적합한 방법을 선택하는 것이 중요합니다. 값의 양이 많아질 것으로 예상되면, 시간 복잡도가 더 낮은 알고리즘을 선택하는 것이 좋습니다.
기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
1
77
2
스택에서 ')'을 만나는 경우
0
78
3
문제가 어디있나요?
0
66
2
변수 or 함수명
0
61
1
침몰하는 타이타닉 문제 질문입니다
0
56
1
AA.py 책점 에러
0
57
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
111
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
110
1
아나그램 비교 코드
0
116
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
160
2
문제 링크가있나여?
0
147
2
채점기 Time Limit Exceeded 오류 문의
1
165
2
동적계획법은 사용하는 문제
0
126
2
제 코드 좀 봐주세요
0
148
1
예외가 존재할 가능성?
0
97
1
3번이 안풀립니다
0
93
0
5번 틀림
0
114
0
오류원인?
0
98
0
리스트 선언
0
106
1
침몰하는 타이타닉(그리디) 문제 질문
0
109
1
알고리즘
0
69
1
코딩테스트
0
92
1
DFS 순서 질문드립니다.
0
128
2
left, right를 사용한 풀이법에 대한 질문입니다
0
91
1