array에서 shift

문제를 풀다 보면 배열에서 shift연산을 해줘야 할 때가 있다. 배열의 시작지점(st)에서 끝지점(end)까지 d칸만큼 움직이려고 한다.

직접 구현하면 아래와 같다.

#include<stdio.h>
const int N = 5;

void shiftLeft(int arr[],int st,int end,int d){
  int tmp[N];
  for(int i=st ; i<=end ; i++)       
    tmp[i] = arr[i];
  for(int i=st ; i<=end-d ; i++)  
    arr[i] = arr[i+d];
  for(int i=0 ; i<d ; i++)
    arr[end-d+i+1] = tmp[st+i];
}

void shiftRight(int arr[],int st,int end,int d){
  int tmp[N];
  for(int i=st ; i<=end ; i++)  
    tmp[i] = arr[i];
  for(int i=st ; i<=end-d ; i++)
    arr[i+d] = tmp[i];
  for(int i=0 ; i<d ; i++)        
    arr[st+i] = tmp[end-d+i+1];
}

int main(){
  int arr[N] = {1,2,3,4,5};

  int d = 1; // d is number of shift distance, must be d <= (end - st + 1);
  int st = 0,end = 4;
  shiftLeft(arr,st,end,d); // 2 3 4 5 1
  // shiftRight(arr,st,end,d); // 5 1 2 3 4

  for(int i = st ; i <= end ; i++) 
    printf("%d ",arr[i]);
}

하지만 c++ STL에서 shift연산을 지원해준다. 바로 algorithm헤더에 있는 rotate() 함수이다. 이 함수는 인자로 rotate(first,middle,last)를 받는다. 구간 [first,middle]를 last뒤에 덧붙여준다고 생각하면 된다.
디폴트 shift 방향은 왼쪽이며, 오른쪽으로 shift 하고 싶다면 역방향 이터레이터인 rbegin(),rend()로 하면 된다.
다만 rotate()함수는 last의 인자로 무조건 배열(벡터)의 마지막 주소값을 주지 않으면 정상적인 작동을 보장하기 어렵기 때문에, array내의 subarray를 shift하려면 위의 코드처럼 직접 구현해야한다.

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 6;

int main(){
    int arr[SIZE] = {0,1,2,3,4,5};
    int n = 6;
    int d = 2;

    rotate(arr,arr+d,arr+n); // 2 3 4 5 0 1

    for(int i=0 ; i<=5 ; i++) printf("%d ",arr[i]);
}

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 10;

int main(){
    vector<int> v = {0,1,2,3,4,5};
    int n = 5;
    int d = 2;

    rotate(v.rbegin(),v.rbegin()+d,v.rend()); // 4 5 0 1 2 3

    for(int i=0 ; i<=5 ; i++) printf("%d ",v[i]);
}