리트코드 - 189. Rotate Array

리트코드 - 189. Rotate Array

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

 

문제 설명

주어진 정수 배열 nums를 오른쪽으로 k단계만큼 회전하는 작업을 수행합니다. 이때 k는 음이 아닌 정수입니다.

의사코드

크기 k만큼의 arr 배열 생성 반복문 시작 (arr 배열 순회)     nums 배열의 뒤에서 k번째부터 k-1, k-2 순으로 arr 배열에 대입 반복문 종료 반복문 시작 (nums 배열의 뒤에서 k + 1번째부터 시작해서 0번째까지 역순으로 진행)     nums 배열의 값을 +k 번째 배열 값에 대입 반복문 종료 반복문 시작 (arr 배열 순회)      arr배열을 nums 배열에 대입 반목문 종료

풀이코드

import java.util.*;

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

        int[] arr = new int[k];

        for (int i = 0; i < k; i++) {
            arr[i] = nums[size - k + i];
        }
 
        for (int i = size - k - 1; i >= 0; i--) {
            nums[i + k] = nums[i];
        }
 
        for (int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
    }
}

코드설명

새로운 arr 배열을 만들어서 그곳에 우선 nums 배열의 k번째부터 끝까지 값을 순차적으로 넣는다.(첫번째 for문)

로테이션되어 떨어져(?) 나갈 값들 이기 때문이다.

그리고 nums 배열의 뒤에서 k+1번째 부분부터 0번까지 역으로 순회하며 k만큼 떨어진 뒤에다가 값을 넣는다.(두번째 for문)

마지막으로 arr 배열에 넣었던 값을 다시 nums 배열에다가 넣어준다.(세번째 for문)

 

처음에 k를 배열의 크기로 나누어 나머지만 놔두는 이유는, ArrayOutOfBound가 발생하기 때문이다.

 

배열이 크기 2짜리라면, k가 2인 경우(두번 돌리면) 두번 돌아가서 원래의 배열이 된다.

예를 들어 {1,2}라는 배열이 있다면, 한 번 돌리면 {2,1}이 되고 두 번 돌리면 다시 {1,2}가 된다.

 

즉, 배열 크기와 k가 같으면 원래의 배열이 되므로 나누기를 하여 나머지를 값이 실제로 돌리는 값이 되기 때문이다. 

 

시간복잡도 - O(n)

공간복잡도 - O(1) (O(k)만큼의 공간이 필요하지만, k는 최대 배열의 크기 -1 이므로 입력에서 이미 정해진 값이다.)

문제를 풀며 생각한 흐름과 배운 점

처음에는 단순히 k만큼 반복하여 순회하는 방법을 생각했다.(예시에도 그렇게 되어있길래..)

import java.util.*;

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

        while (k > 0) {
            int temp = nums[nums.length - 1];
            for (int i = nums.length - 1; i > 0; i--) {       
                nums[i] = nums[i - 1];
            }
            nums[0] = temp;
            k--;
        }
    }
}

하지만 결과는 시간초과....

일일이 순회하는 것은 무조건 시간초과가 날 것 같아서 배열을 분해해서 생각해보기로 했다.

 

처음에는 아래와 같은 코드로 생각을 했는데 자꾸 예외 케이스가 발생했다.

import java.util.*;

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

        for (int i = 0; i < k; i++) {
            arr[i] = nums[size - k + i];
        }
 
        for (int i = size - k - 1; i >= 0; i--) {
            nums[i + k] = nums[i];
        }
 
        for (int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
    }
}

답으로 제출한 코드와 비교해보면 k를 나누는 부분이 없다.

배열의 크기보다 k가 큰 경우 인덱스 값이 음수가 되는 경우가 발생하면서 ArrayOutOfBound가 발생하게 되었다.

예외 케이스를 보면서 k값이 배열의 크기보다 크면 안되겠다는 생각을 하게되어 코드를 추가하였고, 답을 완성하였다.

 

다른코드

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; 
        
        reverse(nums, 0, n - 1); 
        reverse(nums, 0, k - 1); 
        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--;
        }
    }

찾다보니 이렇게 배열을 역순으로 돌린다음, 0부터 k번째까지 뒤집고 k+1번부터 끝까지 다시 뒤집는 방법도 있었다.

신기하게도 이렇게 하면 로테이션 한것과 같은 효과가 나온다.

어떤 원리로 유도되는지 정확하게는 모르겠지만.. 이런 스킬도 알아두면 도움이 되지 않을까 싶다.

 

정리 및 궁금증

배열에 접근할 땐 인덱스가 유효한지 항상 고려해야 하고, 가능하면 이중 반복문은 지양하는 것이 좋을 것 같다.

 

처음 문제를 봤을 때 원형으로 된 판에 숫자를 순서대로 시계방향으로 적고 자르는 방법을 생각했는데 실력이 부족해 코드로 구현하지 못한 것이 아쉽다.

마치 케이스에 숫자를 시계방향 순서로 적어놓고 k에 해당하는 부분을 칼로 잘라서 그걸 펼치는 방법 같은 것 말이다.

아직은 어떻게 만들어야 할지 떠오르지 않으므로 공부를 조금 더 해보고 구현 해봐야겠다