[BOJ-10811][C++] 바구니 뒤집기

 

문제

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

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

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

 

입력

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

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

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

 

출력

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

 

예제 입력 1

5 4
1 2
3 4
1 4
2 2

 

예제 출력 1 

 

3 4 1 2 5

 

알고리즘 분류

• 구현
• 시뮬레이션

 

문제 출처

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

10811번: 바구니 뒤집기

 

---

 

문제 해결 방법

• [단계별로 풀어보기] 문제집에 새로 추가된 문제이다.
• 배열에 대해 이해하고 있으면 쉽게 풀 수 있었던 문제였다.

 

[i, j] 구간의 배열 요소 뒤집기(Reverse)

• 나는 배열(@ary@)의 @i@번째부터 @j@번째까지의 요소를 뒤집는(Reverse) 알고리즘을 다음과 같이 작성하였다.

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

    int cnt, start;

    // Reverse
    cnt = start = 1;
    for (int b = j; b >= i; b--) {
        tmp[cnt++] = baskets[b];
    }

    for (int c = i; c <= j; c++) {
        baskets[c] = tmp[start++];
    }
}

 

단계 1

• @i@가 2이고, @j@가 4라고 가정할 경우, @ary[j]@부터 @ary[i]@까지 거꾸로 배열 요소에 접근하면서 @tmp@ 배열에 축적시켜준다. (축적할 때마다 @tmp@ 배열의 인덱스를 1씩 증가시켜준다. (@tmp[cnt++]@)

배열 \ 인덱스	1	2(i)	3	4(j)	5
ary[5]	1	2	3	4	5
tmp[3]	4	3	2

 

단계 2

• @ary[i]@부터 @ary[j]@까지 순서대로 배열 요소에 접근하면서 @tmp@ 배열의 첫 번째 값부터 하나씩 값을 업데이트 해준다. (축적할 때마다 @tmp@ 배열의 인덱스를 1씩 증가시켜준다. (@tmp[start++]@)

배열 \ 인덱스	1	2(i)	3	4(j)	5
ary[5] (변경 전)	1	2	3	4	5
tmp[3]	4	3	2
ary[5] (변경 후)	1	4	3	2	5

 

코드

#include <iostream>
using namespace std;

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

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

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

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

        int cnt, start;

        // Reverse
        cnt = start = 1;
        for (int b = j; b >= i; b--) {
            tmp[cnt++] = baskets[b];
        }

        for (int c = i; c <= j; c++) {
            baskets[c] = tmp[start++];
        }
    }
}

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

 

관련 문제

[BOJ-10810][C++] 공 넣기