로직을 짜시고 난 뒤에 시간복잡도를 한 번 보시는 연습을 해보세요.
min함수같은 경우에는 배열을 다 흝으면서 그 중 작은 것을 찾는 것이기 때문에 O(n)
data.index(value) = data배열에서 value의 값을 찾는데 O(n)
data.pop(index) = data배열에서 해당 index를 pop한 뒤, 해당 빈자리를 채우기 위해 shift연산이 일어납니다. 최대 O(n)
for문이 N번만큼 돌고 for문 안에서 O(N)만큼 시간복잡도가 생기니 총 시간복잡도는 O(N^2)가 되겠죠?
N이 최대 10만이니 10만 * 10만 = 100억의 시간복잡도를 가집니다.
대충 1억번의 연산이 1초에 일어난다고 하니 100억이면 터무니 없을겁니다.
시간복잡도 개념과 사용하시는 메소드의 시간복잡도가 어떻게 되는지 공부하시는게 좋을 것 같네요.
dbstjdgus0 2년 전
수들 중에서 제일 작은 값 두개를 리스트에서 제거 후 더한 값을 리스트에 추가 후
해당 값들의 합을 출력했습니다!
시간초과 문제는 어떻게 해결하는게 좋을까요...
조언 부탁드리겠습니다!