HackerRank : Left Rotation
Integer 타입이 들어있는 리스트의 요소를 왼쪽으로 하나씩 미는 문제

이슈 배경

List로 풀었을 때 테스트케이스 2개가 시간 초과로 실패하여 List를 Array로 변환 후 같은 로직으로 풀었더니 통과됐다. 단지 List와 Array의 차이인줄 알았으나, 내 알고리즘 자체의 문제였다.
O(N)으로 풀 수 있는 문제인데 O(n^2)으로 해놓고 왜 시간초과야?! 하고 있었음

Array로 풀었을 때

public static List<Integer> rotateLeft(int n, List<Integer> arr) {
    Integer[] array = arr.toArray(new Integer[arr.size()]);
    
    for (int i = 0; i < n; 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);
}

외부 for문은 d만큼 반복하기 위한 반복문이고, 내부 for문은 배열의 원소를 하나씩 이동시키는 반복문이다.
이중 반복문이 사용되어 시간복잡도는 O(n^2)이 된다.

처음에는 ArrayList로 풀었더니 시간 초과가 발생했고, Array로 변경했더니 통과돼서 내 코드에는 문제가 없고, List와 Array의 차이인 줄 알았다.
하지만 데이터 변경 시 시간복잡도는 둘 다 O(1)이라고 나와서 마냥 그런 줄만 알았다. (내 코드는 의심도 하지 않은 채..)

LinkedList로 풀었을 때

public static List<Integer> rotateLeft(int n, List<Integer> arr) {
        LinkedList<Integer> list = new LinkedList(arr); 
        
        for (int i = 0; i < n; i++) {
            list.add(list.poll());
        }
        
        return list;
    }

리스트의 원소가 하나씩 앞으로 당겨질때마다 첫번째 값은 리스트의 마지막으로 가게된다.

그래서, LinkedList를 사용하여 첫번째 값을 삭제함과 동시에 반환되는 값을 리스트의 마지막에 다시 넣었다.

list.add(list.poll());

그럼 이게 Left Rotation 1회전이 된다.

위 동작을 n번 반복하면 O(n)의 시간복잡도를 가지는 알고리즘이 된다.

for (int i = 0; i < n; i++) {
	list.add(list.poll());
}

빅오표기법

GitHub TIL에 정리해서 올려둠

마무리

자료구조와 알고리즘 공부를 하면서 시간복잡도를 간과하고 무지성으로 코드를 쓰고 빅오표기법도 잘 몰랐다 ^^;
이 문제를 Okky에 올렸더니 다른 개발자분들께서 틀린 점을 정확히 짚어주셨다.
틀린 코드를 당당하게 내세우며 엉뚱한 곳에서 원인을 찾으려고 했던 내가 부끄러웠지만 아는 척하고 넘어가는 게 더 비겁한 거라 생각하고 잊지 않으려고 이렇게 기록해두려고 한다.
이제 코테 통과하는 것보다 성능을 생각하면서 문제를 풀길 바란다...!