[leetcode][189] Rotate Array

문제 : leetcode.com/problems/rotate-array/

---

Follow up에 적힌 공간복잡도 O(1)을 목표로 해보자.

예시로 나온 nums=[1,2,3,4,5,6,7], k=3을 예로 들어보면

일단 nums 배열은 모두 reverse 시킨다. nums=[7,6,5,4,3,2,1]

그리고 앞에서 k개의 원소를 reverse 시키고 nums=[5,6,7,4,3,2,1]

k개 이후의 원소들을 다시 reverse 시키면 원하는 배열을 만들 수 있다. nums=[5,6,7,1,2,3,4]

이 때 k는 음수가 아니라는 말만 있고 nums 배열 크기보다 클 수도 있으므로 모듈러 연산해줘야 한다. k = k % |nums|

 

시간복잡도는 O(N). 공간복잡도는 O(1)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/189.%20Rotate%20Array.cpp