C++로 배열을 분할하고 첫 번째 부분을 끝에 추가하는 방법

이 글에서는 배열을 분할한 후, 분할된 첫 번째 부분을 배열의 맨 뒤에 추가하는 방법을 살펴보겠습니다. 예를 들어 배열이 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}라고 가정해 보겠습니다. 이 배열을 두 부분으로 나누는데, 첫 번째 부분은 인덱스 0부터 3까지(분할 크기 4), 두 번째 부분은 나머지 요소들입니다. 첫 번째 부분을 배열 끝에 추가하면 최종 결과는 {4, 5, 6, 7, 8, 9, 0, 1, 2, 3}이 됩니다.

이 문제는 간단한 왼쪽 회전(left rotation) 기법으로 해결할 수 있습니다. 분할 크기 k만큼 반복하면서 매번 첫 번째 요소를 임시 변수에 저장하고, 나머지 요소들을 한 칸씩 앞으로 이동시킨 뒤, 마지막 위치에 저장해 둔 첫 번째 요소를 넣는 방식입니다.

알고리즘

splitArray(arr, n, k)

begin
   for i := 0 to k, do
      x := arr[0]
      for j := 0 to n-2, do
         arr[j] := arr[j+1]
      done
      arr[n-1] := x
   done
end

C++ 코드 예제

#include<iostream>
using namespace std;
void splitArray(int arr[], int n, int k){
   for(int i = 0; i<k; i++){
      int x = arr[0]; //첫 번째 숫자를 임시 저장
      for(int j = 0; j<= n-2; j++){
         arr[j] = arr[j+1]; //요소를 한 칸씩 앞으로 이동
      }
      arr[n-1] = x; //마지막 위치에 첫 번째 숫자 배치
   }
}
main() {
   int data[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   int n = sizeof(data)/sizeof(data[0]);
   int i;
   cout << "Enter split size: ";
   cin >> i;
   splitArray(data, n, i);
   for(int i = 0; i <n;i++){
      cout << data[i] << " ";
   }
}

실행 결과

Enter split size: 4
4 5 6 7 8 9 0 1 2 3

동작 원리 및 시간 복잡도

위 코드는 사용자로부터 분할 크기를 입력받아 splitArray 함수에 전달합니다. 함수 내부에서는 외부 루프가 k번 실행되고, 각 반복마다 내부 루프가 배열의 요소를 한 칸씩 왼쪽으로 이동시킵니다. 따라서 전체 시간 복잡도는 O(n × k)입니다.

배열 크기가 크거나 회전 횟수가 많다면, 반전(reversal) 알고리즘이나 juggling 알고리즘(최대공약수 활용)을 사용하면 O(n) 시간 복잡도로 더 효율적으로 처리할 수 있습니다. 또한 C++ 표준 라이브러리의 std::rotate 함수를 활용하면 한 줄로 동일한 결과를 얻을 수도 있습니다.