[알고리즘] LeetCode - Rotate Array

Rotate Array - LeetCode

문제 설명

• 정수형 배열 nums가 주어진다.
• 배열의 모든 수를 k만큼 오른쪽으로 회전하고 마지막에 있는 수는 제일 앞으로 이동시킨다.

문제 해결

• 논리형 배열 v에 덮어쓴 여부를 체크한다.
• 덮어쓰기 전에 정수형 배열 arr에 저장한다.
• 반복문을 돌면서 다음 자리에 현재 자리의 수를 옮기는데 덮어써진 이력이 있으면 arr에서 값을 가져와서 저장하고 없으면 nums에서 가져와서 저장한다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public void rotate(int[] nums, int k) {
        int N = nums.length;
        int[] arr = new int[N];
        boolean[] v = new boolean[N];

        for (int i = 0; i < N; i++) {
            int next = (i + k) % N;

            if (!v[next]) {
                arr[next] = nums[next];
                v[next] = true;
            } 

            if (!v[i]) {
                nums[next] = nums[i];
            } else {
                nums[next] = arr[i];
            }
        }
    }
}

결과

시간	메모리
3 ms	54.6 MB