Leetcode(Rotate Array)

금일 풀어본 문제는 Reate Array문제이다.

 

url : https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/

 

문제는 아래와 같이 주어졌다.

 

문제에서 요청사항

1. list상에서 가장뒤에있는 숫자를 빼서 리스트 젤 앞으로 이동시키는 작업을 K번 만큼 진행

2. 공간복잡도를 1로만들수 있는 방법중에서 가장 많이 풀어보아라

 

 

첫번째 방법은 주어진 방법 그대로 맨뒤에 있는 값을 젤 앞으로 이동시키는 방법

아래와 같이 공간 복잡도는 1이지만 시간 복잡도는 n^2이여서 timeout발생하여 정답이 아님

- 공간복잡도 : O(1)

- 시간복잡도 : O(n^2)

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

            for (int i=0; i < k; i++){
                before = nums[nums.length-1];
                for (int j=0; j < nums.length; j++){
                    temp = nums[j];
                    nums[j] = before;
                    before = temp;

                }
            }

        }
    }

 

두번째 방법은 복제본을 만들어서 숫자를 바꾸기

1. nums의 첫번째를 복제본의 뒤에서 k번째로, 두번째를 복제본의 뒤에서 k-1번째로 k번 돌면서 진행

2. nums의 k+1번째를 복제본의 첫번째로, k+2번째를 복제본의 두번째로 이런식으로 전체 index길이 - k만큼하여 진행

 

시간복잡도 : O(n)

공간복잡도 : O(n)

 

class Solution2 {
        public void rotate(int[] nums, int k) {
            int numsLength = nums.length;
            int[] copy = Arrays.copyOf(nums, numsLength);

            for (int i=0; i < k; i++){
                nums[i] = copy[numsLength-k+i];
            }
            for (int i=k; i < numsLength; i++){
                nums[i] = copy[i-k];
            }


        }
    }

 

세번째 방법은 복제본을 만들어서 숫자를 바꾸기

1. 리스트 전체를 역순으로 바꾸기

2. 첫번째부터 k번째까지 역순으로 변경

3. K+1번째부터 끝까지 역순으로 변경

 

• 시간 복잡도: O(n) (배열의 길이에 비례)
• 공간 복잡도: O(1) (상수 공간)

 

class Solution {
    public void rotate(int[] nums, int 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) {
        while (start < end) {
            int temp = nums[end];
            nums[end] = nums[start];
            nums[start] = temp;
            start++;
            end--;
        }
    }
}