[백준] 10811번: 바구니 뒤집기 | C++ 풀이

# 문제

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

 

 

---

 

# 풀이

이번 문제에서는 살짝 주춤한 분들이 있을 수도 있겠다.

하지만 잘 생각해보면 어렵지 않은 문제다. 우리는 아직 solved.ac 기준 브론즈 2를 푸는 중이기 때문...

정답 소스코드를 확인하며 차분히 생각해보자.

 

#include <iostream>
using namespace std;

int main(){
    int n, m; // n개의 바구니, m번 순서 변경
    int a, b; // a번째 바구니부터 b번째 바구니의 순서를 역순으로 변경
    
    cin >> n >> m;
    int basket[n+1];
    for(int i=1; i<n+1; i++){
        basket[i] = i;
    }

    while(m--){
        cin >> a >> b;
        if(a != b){
            for(int i=0; i <= (b-a)/2; i++) {
                swap(basket[a+i], basket[b-i]);
            }
        }
    }

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

    return 0;
}

 

우선 문제에서 주어진 대로 n, m, a, b라는 정수 변수를 설정해주었다.

바구니를 놓을 수 있는 크기 n+1의 1차원 배열을 선언하고 for문으로 바구니를 놓아주면 문제를 풀 준비는 끝이다.

크기를 n+1로 선언함은 배열의 인덱스와 바구니 번호를 맞추기 위해서다.

 

 

while(m--){
    cin >> a >> b;
    if(a != b){
        for(int i=0; i <= (b-a)/2; i++) {
            swap(basket[a+i], basket[b-i]);
        }
    }
}

 

m번의 순서 변경동안 a와 b를 받아주는데, 불필요한 for문의 반복을 피하기 위해 a!=b인 경우에만 자리를 변경할 수 있게 하였다.

자리변경에 해당하는 부분은 for문을 보면 된다. 해당 로직은 다음과 같이 생각해볼 수 있다.

 

 

---

 

• 1부터 5번 바구니의 순서를 역순으로 출력해보자.

 

1

2

3

4

5

이때 우리는 '5를 들어 1번 자리에 / 4를 들어 2번 자리에 /  3은 그대로 두고 / 2를 들어 4번 자리에 / 1을 들어 5번 자리에'라고 생각하게 된다.

 

5

2

3

4

1

 

5

4

3

2

1

하지만 이는 양끝에서부터 차례로 위치를 교환해주는 것과 같은 결과다.

그러니까 1번과 5번을 교환 / 2번과 4번을 교환하는 것과 동일한 결과를 보인다. 이때 for문의 조건식 설정만 유의하자. 

 

---

 

 

여기서 자리 교환은 swap 함수를 사용해주었는데,

만약 swap을 사용하지 않고 풀고싶다면 아래와 같이 임시변수를 만들어 교환해주면 된다.

int tmp = basket[a+i];
basket[a+i] = basket[b-i];
basket[b-i] = tmp;

 

 

이후에는 순서를 바꾼 바구니들을 차례로 출력해주면 

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

 

간단하게 해결 가능하다. 바로 결과를 확인해보자.

 

 

 

 

 

---

 

 

10811번: 바구니 뒤집기