LeetCode : 189. Rotate Array

문제 링크

문제 먼저 읽기

• 정수 배열 nums 가 주어집니다.
• 배열을 오른쪽으로 k 번 숫자를 이동시킵니다.

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

• Follow up
  • 최대한 다양한 방법으로 풀어보세요. 적어도 3가지 방식으로 풀 수 있습니다.
  • 제자리에서 O(1) 의 공간 복잡도로 풀 수 있을까요?

 

어떻게 풀까?

생각

• index에 k-1만큼 더해주고 최대값으로 나눈 나머지를 index로 새로운 배열에 입력해 준다면 가장 쉽게 만들 수 있지 않을까?
• 제자리에서 한다면 시간 복잡도가 많이 비효율적이 될 것 같다.

 

수도코드

class Solution {
    public void rotate(int[] nums, int k) {
        int[] origin = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            origin[i] = nums[i];
        } // 배열을 복사한다.
        
        for (int i=0; i<nums.length; i++) {
            int temp = i - k; // 
            nums[i] = origin[temp%nums.length]; // 나머지로 넣어준다.
        }
    }
}

• 1차 이 코드는 통과하지 못했습니다. 음수 index가 발생할 수 있는 경우를 생각하지 못했기 때문에 🥲
• 그래서 음수 처리를 해줘어야 했습니다.

 

제출 코드

• 시간복잡도가 O(2n) 이라 아쉬움이 남습니다.

class Solution {
    public void rotate(int[] nums, int k) {
        int[] origin = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            origin[i] = nums[i];
        } // 배열을 복사한다.
        
        for (int i=0; i<nums.length; i++) {
            int temp = (i - k)%nums.length;
            if (temp < 0) temp += nums.length; // 음수처리
            nums[i] = origin[temp];
        }
    }
}

결과

<aside> 💡 Success

Runtime: 2 ms, faster than 19.56% of Java online submissions for Rotate Array.

Memory Usage: 55.2 MB, less than 88.34% of Java online submissions for Rotate Array.

</aside>

 

다른 풀이 방식과 문제 회고

• 시간복잡도가 좋은 풀이를 확인해보자면.

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // (1) 불필요한 연산을 줄이는 코드
        
        // Reverse the entire array
        reverse(nums, 0, n - 1);
        
        // Reverse the first k elements
        reverse(nums, 0, k - 1);
        
        // Reverse the remaining elements
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

• 불필요한 연산을 줄이는 방식을 더 고민해야겠습니다.
• 그리고 결과물을 분석해서 수학적으로 더 효율적인 방법은 없을까 고민해보면 좋을 것 같습니다.
• 배열을 전체 복사하는 것이 아니라 필요한 최소 숫자만 저장하면 공간복잡도 면에서 훨씬 좋습니다.

class Solution {
    public void rotate(int[] nums, int k) {
        int[] list = new int[nums.length];
        for(int i = 0;i < nums.length;i++){
            list[(i+k)%(nums.length)] = nums[i];
        }
        for(int i = 0;i<list.length;i++){
            nums[i] = list[i];
        }
    }
}