Python에서 list의 append 함수는 시간복잡도가 O(1)이기 때문에 append()를 이용하던 미리 선언하고 값을 지정하던 시간은 별 차이가 없습니다. 그리고 미리 크기만큼 리스트를 선언하는 것은 불필요한 공간을 쓴다는 단점이 있긴 하지만 N의 제한이 매우 큰 것이 아니라면 이것도 별 차이가 없습니다.
본론으로 넘어와서 이 코드가 왜 시간 초과가 나는 지에 대해 설명드리자면 이 코드는 시간복잡도가 O(N2)입니다. 7~27행의 while 문에서 약 N번 반복문이 실행되고, 12~17행/20~25행의 반복문에서 또다시 약 N번의 반복문이 실행되기 때문입니다. O(N2) 정렬은 N의 최대치가 100000인 이 문제에서는 절대 통과할 수 없습니다. 더 효율적인 정렬 방법을 사용해 보세요.
osh1795 2년 전
sort를 이용하지 않고 입력받으면서 하나 하나 비교하면서 리스트에 저장하는 방식으로 문제를 풀었더니 시간 초과가 발생했습니다.
혹시 이 방법의 문제점이나 시간 초과 문제를 해결할 수 있는 방법이 있을까요??
그리고 "append를 이용하는 것"과 "미리 크기만큼 리스트를 만든 다음에 위치를 지정하여 값을 저장하는 것" 2개가 시간 측면이나 메모리 측면에서 차이가 큰가요??