[Misc][Medium] 189. Rotate Array

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

 

Q. 정수배열 nums가 주어질 때, k 만큼 배열을 rotate하여라.

 추가 메모리를 사용하지 말아라. 

 

 

Solution. 

 고전과도 같은 문제이다. 

 

 추가 메모리를 사용할 수 있다면, 간단하다. 

 오프셋 k 만큼 이동시켜 새 버퍼에 쓰면 된다. 

 

 추가 메모리를 쓰지 않으므로, 다른 접근이 필요하고, 이에 대해 알려진 알고리즘을 쓴다. 

 

 배열 전체를 reverse한다. 

 앞에서 k 개 만큼 reverse한다. 

 이후 위치에서 array.Length - k 만큼 reverse한다. 

 

 이것이 결과가 된다. 

 

 만약 문제 질의가 left로 회전하지 않고 right로 회전한다면 어떨까?

 그 경우도 약간의 응용으로 해결 가능하다. 

 

 배열 전체를 reverse한다.

 뒤에서 k개 만큼 reverse한다. 

 처음부터 array.Length-k 만큼 reverse한다.

 

 코드는 로직대로 간단하다. 

 

 다만 k는 배열 길이로 정규화 할 필요가 있다.

public void Rotate(int[] nums, int k) 
{
    k %= nums.Length;
    Array.Reverse(nums, 0, nums.Length);
    Array.Reverse(nums, 0, k);
    Array.Reverse(nums, k, nums.Length-k);
}

 

 

적절한 결과.