Week 1-1. [Array / String] 189. Rotate Array

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Rotate Array - LeetCode

주어진 배열을 오른쪽 방향으로 k 만큼 rotate 하라.

• 입력
  • nums | int arrray := 정수 배열, | nums | ∈ [1, 10^5]
• 출력
  • nums | int arrray := rotate 된 배열, | nums | ∈ [1, 10^5]
• 조건
  • | nums[i] | ∈ [-2^31, 2^31 - 1]
  • | k | ∈ [0, 10^5]

 

🔎 어떤 식으로 접근했는가?

추가 Array 공간을 활용하는 방법을 생각했다.

 

우선 nums 배열의 값을 copied 배열에 복사해둔다.

k만큼 rotate 한 인덱스(=idx)를 구한 뒤, nums[idx]에 copied 배열의 값을 대입한다. 

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

nums의 길이가 최대 100,000이므로 O(N)의 시간 복잡도를 갖는 단일 for문으로 구현할 것이다.

 

📝 의사 코드

n = nums 배열 길이
copied = nums를 복사한 배열

for (0부터; n까지; 1씩 증가) {
	idx = (i + k) % n
    nums[idx]에 copied[i] 대입
}

 

🎯 구현 코드

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] copied = new int[n];
        
        for (int i=0; i<n; i++) {
            copied[i] = nums[i];
        }

        for (int i=0; i<n; i++) {
            int idx = (i+k) % n;
            nums[idx] = copied[i];
        }
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하였으므로 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

N은 최대 100,000이므로 감당할 수 있는 범위이다.

 

보통 1초 제한이라고 할 때, O(N)은 약 1억까지 O(N^2)은 약 1만까지 감당할 수 있다.

따라서 해당 문제를 2중 for문으로 구현한다면 터지게 될 것이다.

 

💡 무엇을/어떻게 개선할 수 있을까?

copied 배열에 값을 복사할 때, 위에서 구현한 것처럼 for문을 이용해 값을 하나씩 대입할 수도 있지만 Arrays.copyOf() 메서드를 사용하면 간단히 같은 동작을 구현할 수 있다.

int n = nums.length;
int[] copied = Arrays.copyOf(nums, n); // 원본 배열, 복사할 길이

 

 

그리고 만약 nums의 길이(= n)가 5라고 가정한다면, 이 때 1 만큼 rotate 하는 것과 6만큼 rotate 하는 것은 동일한 결과를 얻는다.

문제에서 k가 최대 100,000 이니 k %= n 으로 k의 값을 낮추는 것도 효율적으로 계산하는데 도움이 될 것이다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

class Solution {
    public void rotate(int[] nums, int k) {

        int len = nums.length;
        k %= len;

        reverse(nums, 0, len - 1); // step1. 전체 reverse [7,6,5,4,3,2,1]
        reverse(nums, 0, k - 1);   // step2. 0부터 k-1까지 reverse [ 5,6,7,4,3,2,1 ]
        reverse(nums, k, len - 1); // step3. k부터 마지막까지 reverse [ 5,6,7,1,2,3,4 ]
    }

    public void reverse(int[] nums, int start, int end){
        while (start < end){
            // 양 끝 원소 swap 과정 반복
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            
            start++;
            end--;
        }
    }
}

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

while문을 사용하여 시간 복잡도는 O(N)이다.

 

느낀 점

k %= len 으로 불필요한 연산 과정을 줄일 수 있었다.

최적화 할 수 있는 부분을 꼼꼼히 찾는 연습을 해야겠다.