코테 질문 : 배열은 통과, List는 시간 초과 ??

Question

해커랭크 : https://www.hackerrank.com/challenges/array-left-rotation/problem?isFullScreen=trueList 이 주어지면 리스트 안에 있는 값들을 n번 만큼 앞으로 하나씩 미는 문제입니다.List로 풀었을 때 set(index, object)를 사용하여 값을 하나씩 밀었는데 시간 초과가 발생했고,Array로 변환하여 풀었을 땐 통과됐습니다.둘 다 데이터 변경 시 시간 복잡도는 O(1)으로 알고있는데, 왜 List는 시간 초과가 되는걸까요?아래 제 코드 첨부합니다!// Array public static List rotateLeft(int d, List arr) { Integer[] array = arr.toArray(new Integer[arr.size()]); for (int i = 0; i < d; i++) { int temp = array[0]; for (int j = 1; j < arr.size(); j++) { array[j-1] = array[j]; } array[array.length-1] = temp; } return Arrays.asList(array); }// List public static List rotateLeft(int d, List arr) { for (int i = 0; i < d; i++) { int temp = arr.get(0); for (int j = 1; j < arr.size(); j++) { arr.set(j-1, arr.get(j)); } arr.set(arr.size()-1, temp); } return arr; }

메이플비 · Accepted Answer

시간복잡도는 절대적인 런타임 실행속도와는 개념이 다릅니다.어디까지나 어림을 잡기 위한 방법이고, 실제 런타임은 여러가지 다른 요소들에 의해 결정됩니다.그래서 o(log n)의 시간복잡도를 가지는 바이너리 서치를 활용해서 문제를 풀어도, 선형의 (o(n))의 시간 복잡도를 가지는 방법보다 느린 경우도 생기고 하거든요그래서 내부 구현이 어떻게 되어있냐에 따라 시간 복잡도가 같더라도 런타임 속도에는 차이가 생길 수 있습니다.다만 코딩테스트의 경우 이러한것 까지 고려를 해서 설계를 하기 때문에 만약 같은 시간복잡도를 가진 방법으로 시도를 했을때 런타임 속도에 차이가 나도 통과되는것을 보장하기 위해서 어느정도 여유를 줍니다.지금 위에 적으신 문제는 일반적으로 선형 복잡도로(o(n)) 풀이가 가능한 문제인데 푸신 방법은 둘 다 2차 복잡도 (o(n^2))를 가지고 있습니다. 제 예상으로는 둘 중 하나가 이 문제에 설정된 런타임 속도 제한에 턱걸이 해서 통과하고 다른 하나는 그걸 통과 못해서 발생하는 차이 같네요.

Paimon · Answer

지금 짜 놓으신 알고리즘 자체가 O(n^2) 입니다

KJS2020 · Answer

이중 for문인데 O(1)이라구요?해당 소스에서 for문이 없어야 O(1)입니다.~

코테 질문 : 배열은 통과, List는 시간 초과 ??

3개의 답변

기술 목록