[leetcode] 189. Rotate Array

문제

 

---

풀이

첫 번째 예제(nums = [1,2,3,4,5,6,7], k = 3)를 그리면 아래와 같다.

초록색 네모 그룹을 1번 그룹이라고 하고 파란색 동그라미 그룹을 2번 그룹이라고 할 때 결과는 2번 그룹과 1번 그룹의 순서를 서로 바꿔주면 된다.

• 1번 그룹 : 0 ~ k-1
• 2번 그룹 : k ~ input.length-1

다시 그림으로 간략하게 표현하면 다음과 같다.
화살표는 숫자의 오름차순 정렬을 표현했다.

결과가 나오려면 3번의 reverse를 수행해야 한다.

1. 2번 그룹 reverse
2. 1번 그룹 reverse
3. 전체 그룹 reverse

reverse 과정을 그림으로 표현하면 아래와 같다.

---

코드

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

• 공간 복잡도 : O(1)
• : O(n)

최소한 3개의 풀이가 있다고 하니 나중에 다른 풀이법으로 또 풀어봐야겠다.

---

참고

• https://leetcode.com/problems/rotate-array/