1차원 배열의 회전

배열을 회전시키는 방법에는 왼쪽 회전과 오른쪽 회전이 있습니다. 배열 회전은 배열의 요소들을 일정한 방향으로 이동시키고, 배열의 끝 요소들을 다시 시작 부분으로 이동시키는 작업입니다.

1. i는 원래 배열의 인덱스입니다.
2. k는 회전할 단계 수입니다.
3. n은 배열의 길이입니다.

왼쪽 회전 (Left Rotation)

배열을 왼쪽으로 k만큼 회전시키면 각 요소의 새로운 위치는 (i - k + n) % n으로 계산됩니다. 

 

오른쪽 회전 (Right Rotation)

배열을 오른쪽으로 k만큼 회전시키면 각 요소의 새로운 위치는 (i + k) % n으로 계산됩니다.

Code

#include <iostream>
#include <vector>

using namespace std;

// 왼쪽 회전 함수
void leftRotate(vector<int>& arr, int k) {
    int n = arr.size();
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        temp[(i - k + n) % n] = arr[i];
    }
    arr = temp;
}

// 오른쪽 회전 함수
void rightRotate(vector<int>& arr, int k) {
    int n = arr.size();
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        temp[(i + k) % n] = arr[i];
    }
    arr = temp;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};

    cout << "원래 배열: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    leftRotate(arr, 2);
    cout << "왼쪽으로 2만큼 회전한 배열: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    rightRotate(arr, 3);
    cout << "오른쪽으로 3만큼 회전한 배열: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

결과

원래 배열: 1 2 3 4 5
왼쪽으로 2만큼 회전한 배열: 3 4 5 1 2
오른쪽으로 3만큼 회전한 배열: 5 1 2 3 4

---

라이브러리를 사용하여 구현

algorithm 라이브러리를 사용하면 rotate 함수를 사용하여 배열을 회전시킬 수 있습니다.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};

    cout << "원래 배열: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 왼쪽 회전
    rotate(arr.begin(), arr.begin() + 2, arr.end());
    cout << "왼쪽으로 2만큼 회전한 배열: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 오른쪽 회전
    rotate(arr.begin(), arr.end() - 3, arr.end());
    cout << "오른쪽으로 3만큼 회전한 배열: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

결과

원래 배열: 1 2 3 4 5
왼쪽으로 2만큼 회전한 배열: 3 4 5 1 2
오른쪽으로 3만큼 회전한 배열: 5 1 2 3 4

---

부분 배열 회전 (Basket Problem)

부분 배열 회전 문제는 주어진 배열에서 특정 구간을 회전시키는 문제입니다. 백준 10812번 문제를 통해 이 문제를 해결하는 방법을 살펴보겠습니다.

문제 설명

n개의 바구니가 일렬로 놓여있고, m번의 명령으로 각 바구니의 순서를 회전시킵니다. 각 명령은 세 개의 정수 begin, end, mid로 이루어져 있으며, 이 구간을 회전시킵니다.

• begin은 회전 시작 지점입니다.
• end는 회전 끝 지점입니다.
• mid는 회전할 중간 지점입니다. 이 지점을 기준으로 부분 배열을 두 부분으로 나누고, 두 부분을 서로 교환합니다.

구현 방법

1. 배열을 초기화합니다.
2. 각 명령에 따라 부분 배열을 회전시킵니다.
3. 최종 배열을 출력합니다.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;  // n: 바구니의 개수, m: 명령의 개수

    vector<int> baskets(n);

    // 바구니 초기화
    for (int i = 0; i < n; ++i) {
        baskets[i] = i + 1;
    }

    // m개의 명령 처리
    for (int i = 0; i < m; ++i) {
        int begin, end, mid;
        cin >> begin >> end >> mid;
        begin--;  // 인덱스는 0부터 시작하므로 1 감소
        end--;   // 인덱스는 0부터 시작하므로 1 감소
        mid--;   // 인덱스는 0부터 시작하므로 1 감소

        // 부분 배열 회전
        rotate(baskets.begin() + begin, baskets.begin() + mid, baskets.begin() + end + 1);
    }

    // 최종 배열 출력
    for (int i = 0; i < n; ++i) {
        cout << baskets[i] << " ";
    }
    cout << endl;

    return 0;
}