바구니 순서 바꾸기

레벨: 브론즈 2
날짜: 2023년 4월 5일 오후 9:08
문제번호: 10812
알고리즘: 구현, 시뮬레이션

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	6936	4396	3969	65.843%

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다.

도현이는 앞으로 M번 바구니의 순서를 회전시키려고 만들려고 한다. 도현이는 바구니의 순서를 회전시킬 때, 순서를 회전시킬 범위를 정하고, 그 범위 안에서 기준이 될 바구니를 선택한다. 도현이가 선택한 바구니의 범위가 begin, end이고, 기준이 되는 바구니를 mid라고 했을 때, begin, begin+1, ..., mid-1, mid, mid+1, ..., end-1, end 순서로 되어있는 바구니의 순서를 mid, mid+1, ..., end-1, end, begin, begin+1, ..., mid-1로 바꾸게 된다.

바구니의 순서를 어떻게 회전시킬지 주어졌을 때, M번 바구니의 순서를 회전시킨 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에는 바구니의 순서를 바꾸는 만드는 방법이 주어진다. 방법은 i, j, k로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 회전시키는데, 그 때 기준 바구니는 k번째 바구니라는 뜻이다. (1 ≤ i ≤ k ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 바구니의 순서를 회전시킨다.

출력

모든 순서를 회전시킨 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

예제 입력 1

10 5
1 6 4
3 9 8
2 10 5
1 3 3
2 6 2

예제 출력 1

1 4 6 2 3 7 10 5 8 9

---

풀이

c++의 rotate함수를 이용해 풀어보겠다.

rotate(시작 반복자, 첫 위치로 올 forward 반복자, 종료 반복자)
rotate(v.begin(), v.begin()+1, v.end()); // 1칸씩 왼쪽 이동

이를 여기서는

rotate(i,k,j)

로 실행하면 될 것이다.

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

using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    vector<int> A;
    for(int i=0;i<n;i++) {
        A.push_back(i+1);
    }

    int B[m][3];
    for(int i=0; i<m; i++) {
        cin>>B[i][0]>>B[i][1]>>B[i][2];
    }

    for(int i=0; i<m; i++) {
        rotate(A.begin()+B[i][0]-1, A.begin()+B[i][2]-1, A.begin()+B[i][1]); //종료 반복자에는 -1을 해주면 안됨
    }

    for(int i=0; i<n; i++) {
        cout<<A[i]<<' ';
    }

    return 0;
}