[Leetcode Top Interview 150] 189. Rotate Array

난이도 : medium

문제링크

• int 배열인 nums가 주어짐
• 배열을 주어진 k번만큼 오른쪽에서 회전하세요

 

1. 접근법

• k부터 마지막까지 원소들을 미리 저장해둠
• 0부터 마지막-k까지 원소들을 k부터 마지막까지 할당함
• k부터 마지막까지 원소들을 미리 저장해둔 배열에서 꺼내서 할당함

2. 의사코드

public void rotate(int[] nums, int k) {        
    k = k % nums.length;

    if (k == 0 || nums.length == 1) {
        return;
    }

    int[] tmpArr = new int[nums.length-k];
    for (int i = 0; i < nums.length-k; i++) {
        // 1. tmpArr에 0 ~ 오른쪽에서 k번째까지 저장     
    }

    for (int i = nums.length-k; i < nums.length; i++) {
        // 2. 앞에서부터 오른쪽에서 k번째부터 끝까지 요소를 채움
    }

    for (int i = cnt; i < nums.length; i++) { 
		// 3. tmpArr의 요소를 k번째부터 끝까지 채움
    }        
}

 

3. 구현 코드

public void rotate(int[] nums, int k) {        
    k = k % nums.length;

    if (k == 0 || nums.length == 1) {
        return;
    }

    int[] tmpArr = new int[nums.length-k];

    int cnt = 0;
    for (int i = 0; i < nums.length-k; i++) {
        tmpArr[cnt++] = nums[i];            
    }

    cnt = 0;
    for (int i = nums.length-k; i < nums.length; i++) {
        nums[cnt++] = nums[i];
    }

    int cnt2 = 0;
    for (int i = cnt; i < nums.length; i++) { 
        nums[i] = tmpArr[cnt2++];
    }        
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 노드를 순회함
• 공간복잡도 : O(n) - k 개의 원소를 새 배열에 저장해야 함

 

5. 개선점

• 공간복잡도를 O(1)로

 

6. 회고

• 도저히 생각이 안나 풀이를 찾아보았다

public void solutionRotate(int[] nums, int k) {
        k = k % nums.length;

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

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

(출처 : NickWhite)

• 배열의 길이만큼 회전하는 것은 그대로의 결과이므로 모듈러 연산으로 k를 줄임
• k번째부터 마지막까지 원소를 앞으로 밀어준다는 것은 이와 같음
  • 전체를 reverse로 정렬
  • 0~k-1까지 reverse로 정렬
  • k~마지막까지 reverse로 정렬