[Leetcode] 189. Rotate Array - JS

https://leetcode.com/problems/rotate-array/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
- 정수 배열 nums
- k 단계만큼 오른쪽으로 회전시켜라.
- 반환하지 말고 nums를 제자리에서 수정해라.

제한사항
--------------------
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5

 

 

2. 접근 방법 및 풀이

✅ Key Point
k 스텝만큼 이동한다는 의미에서 유추할 수 있는 부분은 
k 가 nums.length 보다 큰 경우는 nums.length로 나눈 나머지와 같다.

k = k % nums.length 를 도출할 수 있다.
즉, nums.length = 7일 때, k = 3,10,17,24.. 모두 동일하다고 볼 수 있다.

k를 기준으로 변경 전, 변경 후 배열을 비교해보면 접근 방법을 구할 수 있을 것 같다.

 

 

1. 다른 배열에 저장하는 방식

Solution 1.
------------------
1. 새로운 배열 rotated를 선언하여 k 스텝만큼 이동한 요소를 배치한다.
2. nums 배열의 인덱스에 맞게 rotated 배열의 요소를 할당한다.

 

 

var rotate = function(nums, k) {
    let n = nums.length;
    let rotated = [];
    k = k % n;

    for (let i = 0; i < n; i++) {
        rotated[(i + k) % n] = nums[i]
    }

    for (let i = 0; i < n; i++) {
        nums[i] = rotated[i]
    }
}

 

위 풀이의 복잡도 분석은 아래와 같다.

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

 

2. k를 기준으로 앞 배열, 뒤 배열의 위치 변경

Solution 2.
------------------
k 스텝만큼 이동한 배열과 이전배열을 비교한다.

nums = [1,2,3,4,5,6,7], k = 9 (나머지 값이 2인 값과 동일)

 * * * * * # #
[1,2,3,4,5,6,7]
[6,7,1,2,3,4,5]
 # # * * * * *
     k

기존 nums 배열을 k를 기준으로 slice 하여 배치를 변경하여 만들 수 있다.

1. temp 변수에 k를 기준으로 slice하여 배치를 변경한 배열을 할당한다.
2. nums 인덱스에 맞게 temp 요소를 할당한다.

- k가 0일 때는 반복문을 순회할 필요가 없으니 k !== 0 조건을 추가하여 최적화를 진행했다.

 

 

var rotate = function (nums, k) {
    let n = nums.length;
     k = k % n;
     if (k !== 0) {
        let temp = nums.slice(-k).concat(nums.slice(0, -k));
        for (let i = 0; i < n; i++) {
            nums[i] = temp[i]
        } 
     }
}

 

위 풀이의 복잡도 분석은 아래와 같다.

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

 

 

3. k를 기준으로 앞 배열, 뒤 배열의 순서 변경 _ 공간복잡도 O(1)

Solution 3.
------------------
Solution 2. 와 비슷하지만 slice로 새 배열을 만드는 것이 아니라 in place 방식을 사용한다.

1. 전체 배열을 뒤집는다.
2. k 기준 앞, 뒤 배열을 뒤집는다.

nums = [1,2,3,4,5,6,7] k = 2;

1. 전체 배열 뒤집는다. -> [7,6,5,4,3,2,1]
2. k 기준 앞 배열 뒤집는다. -> [6,7,5,4,3,2,1]
3. k 기준 뒤 배열 뒤집는다. -> [6,7,1,2,3,4,5]

 

 

var rotate = function (nums,k) {
    let n = nums.length;
    k %= n
    const reverse = (left, right) => {
        while (left < right) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++;
            right--;
        }
    }

    if (k !== 0) {
        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }
}

 

1, 2번 풀이와 달리 reverse 함수를 구현하여 in-place 방식으로 nums 배열 제자리에서 위치를 변경해주었다.

 

위 풀이의 복잡도 분석은 아래와 같다.

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

나의 실패한 풀이

접근방법
--------------------
오른쪽으로 이동 시키려면 어떻게 할까?
=> 현재 인덱스에 k만큼 더해서 배치한다.

1. 위치 이동시킬 포인터(j)를 선언
2. 현재 값 curr 선언
3. 배열 길이만큼 순회하면서
    - 매 순회 시 포인터(j)가 배열의 길이를 초과하는지 체크
    - 포인터만큼 이동한 위치의 값을 next에 할당
    - 포인터 위치의 값을 curr로 수정
    - curr 값 업데이트
    - 포인터(j) k 스텝만큼 이동

* 예외의 경우, nums = [1,2,3,4], k = 2이면,
첫번째 순회 때 값이 마지막 순회때까지 동일한 값으로 업데이트 되지 않는다.
curr = 1
next = 3

따라서, nums.length와 k가 짝수일 때
1. 배열의 절반까지만 순회한다.
2. 배열의 현재 인덱스 요소와 k 스텝 이후의 요소를 교환한다.

위 방식대로 했을 때, nums = [1,2,3,4,5,6] k=2를 실행하면
[3, 4, 5, 2, 1, 6] 으로 잘못된 값이 나온다.

기존 방식대로 하되, curr 값을 바꿔가면서 해야한다.

😅 Failed...

 

하지만 위 방법대로 진행해보니 가독성도 떨어지고

나중에는 Edge Case를 해결하기 위해서 코드를 수정하고 있어서

포기하고 해설지를 참고하였다.