리트코드 189. Rotate Array JAVA

문제

문제 해석

이 문제를 해결 하는 방법은 총 3개가 있다고 한다.

1. Queue를 이용해서 데이터를 넣고 로테이션을 돌려서 탈출 시켜라
   이건 문제에서 원하는 학습 방법은 아닌 것 같지만 사용해보고자한다.
2. 쪼개서 생각하기
   이전에 풀었던 문제인 Majority Element 를 학습하며 찾은 방법 중 쪼개서 찾는 방법이 있었다. 이런 것 처럼 여러 과정으로 쪼개서 문제를 푼다면 풀 수 있다. (이 전 캠프에서 학습했던 것 적용)

시간을 더 줄일 수 있는 방식이 있는데 아직 방법을 찾지 못했다.

방법 1번 Queue 이용

수도 코드

큐 생성
배열 전부 큐에 삽입
k %=length
length - k 만큼 빼서 넣어준다.

구현 끝나고 nums에 모두 넣어준다.

간단한 코드다.
큐의 원리를 이용해서 문제를 해결한 것으로 선입 선출을 이용했다.
하지만 이 방법은 속도도 별로고, 메모리도 많이 사용한다.

이 방법을 사용해서 해결한 뒤 다시 한번 코드를 생각했었다.

코드

class Solution {
    public void rotate(int[] nums, int k) {
        Queue<Integer> queue = new LinkedList();
        k %= nums.length;
        for (int num : nums) {
            queue.add(num);
        }
        for(int i = 0 ; i < nums.length -k ; i++){
            queue.add(queue.poll());
        }
        int i = 0;
        while(!queue.isEmpty()){
            nums[i++] = queue.poll();
        }
    }
}

이 방법을 사용한 이후에도 하나하나 변경해서 문제를 해결하게 로직을 구현했는데 마지막 테스트 케이스에서 시간 초과가 뜬다.

방법 2 reverse 이용

이 방법을 사용하기 전에 가장 먼저 원했던 것이 추가적인 자료구조를 생성하지 않고 문제를 해결하는 것이다.
다행히 유사한 문제를 풀었던 기억이 난다.
다만 기억이 나는게 리버스를 이용해서 풀었다는게 다였다.

코드를 구현하기 위해 A4용지 4장은 더 쓴 것같다.

로직 설명 & 수도코드

로직을 먼저 설명하자면

1. 일단 싹다 뒤집어라
   • 싹다 뒤집으면 뒤에 있는 것이 앞으로 오고, 앞에 있는 것이 뒤로 간다
     그림으로 설명하면 조금 더 쉬운데 나는 이걸 쪼개기를 위한 준비단계라고 생각한다. 그림은 추 후 첨부 할 수 있으면 첨부하겠다.
2. 앞에서 부터 k-1 번째까지 뒤집는다.
   • 배열은 0번지부터 시작하기 때문이다.
   • k-1번지까지의 정렬이 모두 작동 된다.
3. 나머지 부분끼리 뒤집는다.
   • 나머지에 있는 요소 끼리 뒤집는다면 거기서 순서를 맞출 수있다.

이걸 보면 어느정도 뭘 설명하려고하는지 이해할 수 있을 것이다.

일단 전체 리버스를 한다. 이유는 어차피 로테이션을 돌리면 뒤에 있는 값들이 앞으로 오기 때문에 그걸 먼저 맞춰준건다.

이 후 k-1번째까지 다시 리버스를 건다. 이를 통해 로테이션 했을 때 처럼 값의 순서를 맞춰준다.

나머지를 리버스한다.

이를 통해 원하느 값을 얻을 수 있다.

 

내가 만든 수도 코드

   리버스 메서드를 만든다(어디서부터 어디까지 리버스할 것인가 만들어준다.)
    while () 조건문에 따라 탈출하기 때문에 for가 아닌 while을 사용
    swap 처럼 tmp를 만들어 연결 

    k를 길이로 나눈 나머지로 변경

    리버스 총 3번 진행
    1. 전체 리버스
    2. 앞에서부터 k-1번까지 리버스
    3. 나머지 리버스

코드

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length == 1) return;

        k = k % nums.length;

        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

속도가 빠를 것이라고 생각했는데 역시 첫번째 방식보다 6ms나 빠르다.

코드 구현 이후 0ms가 나오는 코드를 찾아 봤다.

class Solution {
     public static void reverse(int nums[], int i, int j){
        int li = i;
        int ri = j;

        while(li < ri){
            int temp = nums[li];
            nums[li] = nums[ri];
            nums[ri] = temp;

            li++;
            ri--;
        }
    }
    public void rotate(int[] nums, int k) {
        k = k % nums.length; 
        if(k < 0){ 
            k += nums.length;
        }
        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }
}

음 내가 만든 코드랑 크게 다른점이 없는 것같다.
rotate에 있는 if 조건 때문인가? 라는 생각도 했지만 어차피 검증 하나 더한다고 1ms나 차이날 것이라고 생각하지 않는다.
그렇다면 reverse를 할때 나는 배열에 인덱스를 넣으면서 ++ 를 해줬고 위의 코드는 나중에 ++를 해줬다.
그랬더니 2ms로 변경되었다.

내가 예상했던 곳에서는 큰 차이를 주지 못했다.
그렇다면 if()문 때문인가? 하고 if문을 제거했다.
그랬더니 시간이 0ms로 변경되었다.

위의 코드도 if문을 사용했고 내가 만든 코드도 if문을 사용했다.
그렇기 때문에 복잡도에서 차이가 별로 없을 것이라고 생각했는데 차이가 난다.
그것은 뭔가 내가 어디서 실수를 한 것이 있지 않나 싶다.