[C++] 배열 안을 함수 한 번에 회전시켜보자! rotate

종종 비트마스킹을 활용한 다이나믹 프로그래밍이나 요세푸스 문제, BFS 등등 배열을 반시계 방향으로 $k$번 회전시켜야 할 경우, 다음과 같은 방법을 활용하였다.

 

다음 코드는 vector<int> vec를 $k = 1$만큼 회전시킨다고 할 때, C++의 함수 swap를 활용하면 다음과 같이 작성할 수 있다.

 

for (int i = 0; i < (int)vec.size()-1; i++) {
    swap(vec[i], vec[i+1]);
}

 

만약, $k > 1$이라면 새로운 container를 만들어, 나머지 연산을 활용하여 회전 이후 해당하는 위치에 새로 데이터를 담을 수 있다. 그러나, 이 경우 불필요하게 배열의 크기만큼 새로운 공간을 할당해야 하여 불편하다.

 

vector<int> vec;
vector<int> new_vec;
 
for (int i = 0; i < (int)vec.size()-1; i++) {
    new_vec[i] = vec[(i+k) % vec.size()]
}

 

이 경우 한 줄의 코드로 위의 작업을 한 번에 할 수 있는 함수가 있으니, rotate 되시겠다.

 

1. rotate

(※ https://www.cplusplus.com/reference/algorithm/rotate/ 에서 함수에 대한 정보를 확인할 수 있다.)

 

C++의 알고리즘 관련이 담긴 헤더 <algorithm.h>에서의 rotate 함수는 다음과 같은 구조를 가진다.

 

ForwardIterator rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)

 

rotate는 3개의 인자를 받고 1개의 값을 반환한다.

 

• ForwardIterator first : 배열이나 어떤 container의 자료형의 시작부 혹은 포인터
• ForwardIterator middle: 배열이나 어떤 container의 자료형의 first가 회전되어 들어갈 자리의 시작부 혹은 포인터
• ForwardIterator pred : 배열이나 어떤 container의 자료형의 끝부 혹은 포인터

  ---

• Return Value : 배열이나 어떤 container의 자료형의 회전 이전의 시작부 혹은 포인터

구체적으로 이 함수의 역할을 말하자면, 범위 [first, last)에서의 데이터를 middle부터 시작하여 차례로 넣는 다고 생각하면 된다. 만약 이해가 안 된다면, 같은 역할을 하는 코드를 작성하면 다음과 같이 작성할 수 있다.

 

template <class ForwardIterator>
void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last) {
  ForwardIterator next = middle;
 
  while (first!=next) {
    swap (*first++,*next++);
 
    if (next==last) {
        next=middle;
    } else if (first==middle){
        middle=next;
    }
  }
}

 

쉽게 말해, 배열 안의 자료형을 (middle-first) 거리만큼 회전시켜 주는 함수라 생각할 수 있다.

 

2. 예제 코드

위의 코드에서 새로운 배열을 만들지 않고 $k$번 회전시키는 코드를 작성하면 다음과 같다.

 

rotate(vec.begin(), vec.begin()+k, vec.end());

 

매우 간단하게 한 줄로 끝낼 수 있다. 이처럼 특정 배열이나 container에서 데이터를 $k$번만큼 옮길 일이 있으면 활용할 수 있다.

 

만약, 시계 방향으로 회전하고 싶으면, $vec.size() - k$로 반시계방향으로 회전 방향을 바꾸고 회전시키면 된다.

 

3. 주의할 점

1.

함수의 인자의 순서에 주의하여야 한다. [first -> middle -> last] 순으로 작성해야 하므로, 각 인자에 맞는 iterator를 넣어주자.

 

2. 

함수 내부적으로 swap을 활용하여 구현이 되어 있기에, swap을 활용할 수 있는 데이터가 담겨있어야 한다. (구체적으로 말하면, move-constructible & move-assignable인 자료형이어야 한다. 즉, 새로운 공간에 담을 수 있는 자료형이어야 한다.)

 

3.

만약, 배열의 범위를 초과하여 index에 접근할 경우 undefined behavior가 발생할 수 있다.

 

rotate 함수는 배열의 처음부터 끝까지 선형적으로 접근하기에 함수의 시간 복잡도는 배열의 길이인 $O(n)$을 가진다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!