[BOJ-10812][C++] 바구니 순서 바꾸기

문제

도현이는 바구니를 총 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

 

 

알고리즘 분류

• 구현
• 시뮬레이션

 

문제 출처

https://www.acmicpc.net/problem/10812

10812번: 바구니 순서 바꾸기

 

---

 

문제 해결 방법

• [단계별로 풀어보기] 문제집에 새로 추가된 문제이다.
• 문제의 설명을 잘 이해하면 풀 수 있었던 문제였다.

 

문제 해결의 원리

• 문제 해결의 원리를 이해하면 다음과 같다.
• @i@번째 값부터 @j@번째 값까지의 요소를 @k@번째의 값 기준으로 회전을 수행한다.

회전 전	i	i + 1	…	k - 1	k	k + 1	…	j - 1	j
회전 후	k	k + 1	…	j - 1	j	i	i + 1	…	k - 1

 

• 예를 들어, 다음과 같이 입력을 받는다고 가정하자.

10 1
1 6 4

• 그러면 우선 다음과 같이 길이가 10인 배열(@baskets@)에 인덱스 1부터 10까지 1부터 10이 들어가게 된다.

baskets[1]	baskets[2]	baskets[3]	baskets[4]	baskets[5]	baskets[6]	baskets[7]	baskets[8]	baskets[9]	baskets[10]
1	2	3	4	5	6	7	8	9	10

• begin(@i@)는 1, end(@j@)는 6, mid(@k@)는 4이므로 문제의 조건대로 회전을 수행하면 다음과 같다.

baskets[1]	baskets[2]	baskets[3]	baskets[4]	baskets[5]	baskets[6]	baskets[7]	baskets[8]	baskets[9]	baskets[10]
4	5	6	1	2	3	7	8	9	10

 

• 이러한 회전이 일어나도록 알고리즘을 작성해주면 된다.
• 나는 @k@를 기준으로 ① k부터 j까지, ② i부터 k-1까지의 값들을 순서대로 @tmp@배열에 넣은 후, 나중에 기존의 배열(@baskets@)에서 @i@부터 @j@까지의 위치의 값들을 @tmp@ 배열에 있는 값들로 바꿔주도록 하는 알고리즘을 작성하였다.
  
  • 이 때, for 문에 @tmp@ 배열의 인덱스 크기 만큼의 값들이 대체되도록 조건을 넣어주었다. (@idx != cnt@)

void Reverse(int begin, int end, int mid) {
    int cnt = 1;

    for (int i = k; i <= end; i++) {
        tmp[cnt++] = baskets[i];
    }
    
    for (int i = begin; i < k; i++) {
        tmp[cnt++] = baskets[i];
    }

    for (int i = begin, idx = 1; (i <= end) && (idx != cnt); i++, idx++) {
        baskets[i] = tmp[idx];
    }
}

 

코드

#include <iostream>
using namespace std;

int N, M, i, j, k;
int baskets[101];
int tmp[101];

void Initialize() {
    for (int i = 1; i <= 100; i++) {    
        baskets[i] = i;    // 1번째부터 100번째 바구니에 1부터 100까지의 숫자 넣기
    }
}

void Reverse(int begin, int end, int mid) {
    int cnt = 1;

    for (int i = k; i <= end; i++) {
        tmp[cnt++] = baskets[i];
    }
    
    for (int i = begin; i < k; i++) {
        tmp[cnt++] = baskets[i];
    }

    for (int i = begin, idx = 1; (i <= end) && (idx != cnt); i++, idx++) {
        baskets[i] = tmp[idx];
    }
}

void Input() {
    cin >> N >> M;

    for (int a = 1; a <= M; a++) {
        cin >> i >> j >> k;

        Reverse(i, j, k);
    }
}

void Solution(int *ary) {
    for (int i = 1; i <= N; i++) {
        cout << baskets[i] << " ";
    }
}

void Output() {
    Solution(baskets);
}

void Solve() {
    Initialize();
    Input();
    Output();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [심화 1]
• 브론즈II