[Array/C++] Rotate Array

 

k만큼 이동시킨 배열을 출력하는 문제이다.

 

솔직히 그냥 문제 해결만 하는 거면 쉽게 풀려서 굳이 포스트 올릴 필요가 없다.

왜?? 똑같은 사이즈의 빈 배열 하나 더 만들어서 k만큼 미뤄서 값 채우면 되니까 말이다.

(아차차 여기서의 아주아주 기본 아이디어는 배열의 크기를 넘어가는 인덱스에 대해서 modular 연산을 쓰는 것)

 

하지만.. Follow up question을 보면 공간복잡도를 O(N)이 아니라 (즉 위의 방법 말고) 

O(1)로 원래 배열만을 가지고 이동시켜보라고 유도하고 있다.

이 과정에서 reverse를 이용해서 k만큼의 슬라이싱을 해보라고 권장하고 있다.

(도오대체 reverse 생각은 어떻게 해야 나올 수 있는 걸까...

색다른, 효율적인 풀이 볼 때마다 나의 부족함이 아주 잘 느껴진다...)

 

처음에 배열 하나만 쓰라고 했을 때는 tmp 변수로 이전 걸 저장하고, 다음에 옮기고 저장하고를 반복해야하나 싶었다.

근데 이건 k가 1이 아니라면 tmp라는 배열로 관리해야하고, 이러면 첫 번째 풀이랑 달라지는게 없었다.

그래서 두 번째 도전으로 k배수 만큼 반복문을 점프해서 구현해나 싶었는데, 반복문의 종료 조건을 찾는데 꽤 애를 먹었다..

 

그렇게 시간을 쓰다가 힌트를 통해 알게 된 reverse 방식.

어떻게 reverse로 k만큼의 이동을 구현할 수 있을까!

->> 직접 해보면서 규칙을 찾아야 하는 것 같다

---

Reverse 규칙 찾기 

 

그러면 이제 k가 이 배열의 사이즈보다 크면 어떨지를 봐야겠다.

문제에서도 k의 범위는 10^5까지 가능하니까 말이다.

k를 k%배열의사이즈로 모듈러 연산을 해준다면 위와 같은 규칙이 적용된다.

규칙 >> 뒤에서 k개 만큼 앞으로 오고, 나머지 뒤로 보내기

 

그러면 이제 k만큼 앞으로 어떻게 보내느냐가 관건이겠다.

이 때 또 추가 배열을 쓴다면 그건 공간복잡도가 O(1)이 아니니까!

 

그래서 전체 배열을 reverse해서 뒤에 있는 애들이 앞으로 오게 해주는 것으로 시작한다.

---

예를 들어 k가 4일 때를 보자.

먼저 전체 배열을 reverse하자

1234567 - > 7654321

 

그러면 7654를 4567로 바꾸고 싶고,

4321은 순서를 1234로 바꾸고 싶다.

이 때 바꾸고 싶은 애들의 크기 기준은 k이다.

 

7654321에서 앞에서부터 k개를 반대로 돌리고

그 나머지도 다시 반대로 돌리고 싶은 것!

 

reverse(arr.begin(), arr.end()) ➡️ 7654321

reverse(arr.begin(),arr.begin()+k) ➡️ 45674321 

reverse(arr.begin()+k,arr.end()) ➡️ 45671234

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k=k%nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

 

규칙을 잘 찾아보자!!