LeetCode - 배열 회전

문제 설명

배열이 주어지면 배열을 k 단계만큼 오른쪽으로 회전합니다. 여기서 k는 음수가 아닙니다.

다음에서 가져온 문제 설명: https://leetcode.com/problems/rotate-array/ .

예 1:

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]

예 2:

Input: nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

Explanation:
rotate 1 steps to the right: [99, -1, -100, 3]
rotate 2 steps to the right: [3, 99, -1, -100]

제약:

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

설명

무차별 대입 솔루션

무차별 접근 방식은 임시(임시) 배열을 만들고 첫 번째 k 요소를 임시 배열에 저장하는 것입니다. 그런 다음 나머지 배열을 k 위치만큼 이동하고 tmp 배열을 원래 배열에 다시 추가합니다.

흐름은 아래와 같습니다.

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

1) Store the first k elements in a temp array
   temp[] = [1, 2]

2) Shift rest of the nums[]
   nums[] = [3, 4, 5, 6, 7, 6, 7]

3) Store back the k elements
   nums[] = [3, 4, 5, 6, 7, 1, 2]

위 방법의 시간 복잡도는 O(N)이고 공간 복잡도는 O(k)입니다.

하나씩 회전

추가 공간을 사용하지 않으려면 배열 요소를 하나씩 회전할 수 있습니다.

배열의 첫 번째 요소를 임시 변수에 저장하고 nums[1]을 nums[0]으로, nums[2]를 nums[1]로... 마지막 요소 nums[n - 1]이 nums[로 이동할 때까지 이동합니다. 엔 - 2].

위의 절차를 k 번 반복합니다.

위의 접근 방식의 시간 복잡도는 O(N*k)이고 공간 복잡도는 O(1)입니다.

배열 반전

문제는 배열을 부분적으로 반전시켜 O(N) 시간 안에 해결할 수 있습니다. part1 = nums[0..k - 1] 및 part2 = nums[k..n - 1]의 두 부분으로 배열을 고려합니다.

part1 배열에 있는 요소를 뒤집습니다. 그런 다음 part2 배열 요소를 뒤집습니다. 결국 전체 배열을 뒤집습니다.

이 솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 확인해 봅시다.

// rotate(nums, k)
- set n = nums.size()

- return if n == 1 or k == 0

- update k = k % n
  This is done when k is greater than n.
  eg n = 8, k = 12
  k = k % n
    = 12 % 8
    = 4

- call reverseArray(nums, 0, n - 1)
- call reverseArray(nums, 0, k - 1)
- call reverseArray(nums, k, n - 1)

// reverseArray(nums, start, end)
- while start < end
  - swap(nums[start], nums[end])
  - start++
  - end--

C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    void reverseArray(vector<int>& nums, int start, int end) {
        while(start < end) {
            std::swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 1 || k == 0) {
            return;
        }

        k = k % n;
        reverseArray(nums, 0, n - 1);
        reverseArray(nums, 0, k - 1);
        reverseArray(nums, k, n - 1);
    }
};

골랑 솔루션

func reverseArray(nums []int, start, end int) {
    for start < end {
        tmp := nums[start]
        nums[start] = nums[end]
        nums[end] = tmp
        start++
        end--
    }
}

func rotate(nums []int, k int)  {
    n := len(nums)

    if n == 1 || k == 0 {
        return
    }

    k = k % n

    reverseArray(nums, 0, n - 1)
    reverseArray(nums, 0, k - 1)
    reverseArray(nums, k, n - 1)
}

자바스크립트 솔루션

var reverseArray = function(nums, start, end) {
    while(start < end) {
        let tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
        start++;
        end--;
    }
}

var rotate = function(nums, k) {
    let n = nums.length;

    if( n == 1 || k == 0 ) {
        return;
    }

    k = k % n;
    reverseArray(nums, 0, n - 1);
    reverseArray(nums, 0, k - 1);
    reverseArray(nums, k, n - 1);
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

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

// rotate function
Step 1: n = nums.size()
          = 7

Step 2: n == 1 || k == 0
        7 == 1 || 3 == 0
        false

Step 3: k = k % n
          = 3 % 7
          = 3

Step 4: reverseArray(nums, 0, n - 1)
        reverseArray(nums, 0, 6)

// reverseArray(nums, start, end)
Step 5: while start < end
        0 < 6
        true

        swap(nums[0], nums[6])
        nums = [7, 2, 3, 4, 5, 6, 1]

        start++
        start = 1
        end--
        end = 5

Step 6: while start < end
        1 < 5
        true

        swap(nums[1], nums[5])
        nums = [7, 6, 3, 4, 5, 2, 1]

        start++
        start = 2
        end--
        end = 4

Step 7: while start < end
        2 < 4
        true

        swap(nums[2], nums[4])
        nums = [7, 6, 5, 4, 3, 2, 1]

        start++
        start = 3
        end--
        end = 3

Step 8: while start < end
        3 < 3
        false

// rotate function
Step 9: reverseArray(nums, 0, k - 1)
        reverseArray(nums, 0, 2)

// reverseArray(nums, start, end)
Step 10: while start < end
         0 < 2
         true

         swap(nums[0], nums[2])
         nums = [5, 6, 7, 4, 3, 2, 1]

         start++
         start = 1
         end--
         end = 1

Step 11: while start < end
         1 < 1
         false

// rotate function
Step 12: reverseArray(nums, k, n - 1)
         reverseArray(nums, 3, 6)

// reverseArray(nums, start, end)
Step 13: while start < end
         3 < 6
         true

         swap(nums[3], nums[6])
         nums = [5, 6, 7, 1, 3, 2, 4]

         start++
         start = 4
         end--
         end = 5

Step 14: while start < end
         4 < 5
         true

         swap(nums[4], nums[5])
         nums = [5, 6, 7, 1, 2, 3, 4]

         start++
         start = 5
         end--
         end = 4

Step 15: while start < end
         5 < 4
         false

// rotate function
no more steps to execute

We return the final array as [5, 6, 7, 1, 2, 3, 4].