파이썬은 1초에 2000만 = 20,000,000 번 연산이 가능하다고 생각해두면 좋다.
따라서 시간제한이 1초, n = 100,000 (10만) 이라고 할 때
O(N^2) 으로 알고리즘을 짜게 되면 10,000,000,000 = 100억 번의 연산이 필요하므로, 시간초과가 나게 된다.
이 경우엔 O(NlogN) 으로 알고리즘을 짜야 1,600,000 번의 연산으로 수행 가능하다. (log 100,000 = 약 16)
일단 이것만 꼭 알아두자 1초에 2000만
5초에 1억번 계산할 수 있다.
따라서 N의 범위에 따라 시간복잡도를 생각하면서 문제를 풀어 봐야겠다.
군도리