백준 10811 - 바구니 뒤집기 (c++)

Haribo·2023년 6월 28일

c++ 백준문제 풀기

목록 보기

1/1

문제

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

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

출력

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

요약

배열 하나 만들고 역순으로 작업할 배열 범위를 사용자가 지정한 후 작업할때 마다 출력하지 않고 모든 작업이 끝난 후 해당 결과를 출력하는 문제

reverse 함수 사용법.

직접 역순 함수를 구현해도 되지만 있는 바퀴를 다시 만들 필요가 없다는 말과 같이 c++에서 제공하는 기능을 이용하자.

reverse함수를 사용하기 위해서는 아래와 같이 include 시켜서 사용한다.

#include <iostrem>
#include <algorithm>

전체 소스코드 내용

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    // n은 바구니 크기 정하기, m은 바꾸는 횟수
    int n, m;

    cin >> n >> m;
    int *arr = new int[n + 1];

    // 바구니 초기화 하기
    for (int i = 1; i <= n; i++)
    {
        arr[i] = i; // 공의 번호와 바구니 번호를 동일하게 만들기
    }

    // 공 바꾸기
    for (int i = 0; i < m; i++)
    {
        int num1, num2;
        cin >> num1 >> num2;

        std::reverse(arr + num1, arr + num2 + 1);
    }

    // 바구니 출력하기
    for (int i = 1; i <= n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

소스 코드 중 reverse에서

std::reverse(arr + num1, arr + num2 + 1);

끝에 +1을 해주는 이유는 끝 인덱스 까지 적용시키기 위해서다.

만약 +1을 하지 않을때 예를 들면 아래와 같다.

5개의 요소{1,2,3,4,5}가 있는 배열 nums가 있다고 하자.
reverse함수에서 "반복자"라는 게 나오는데 c++는 이것을 사용한다.
내가 만약 끝 반복자에 +1을 하지 않았다고 해보자.

배열 요소 = {1,2,3,4,5}
시작 반복자 : nums + start -> 인덱스1(값2를 가르킴)
끝 반복자 : nums + end -> 인덱스3(값4를 가르킴)

여기서 start, end는 위에 코드에서 num1, num2부분이다.
시작과 끝 범위를 설정할때 사용한다.

요약하면 +1을 안쓰면 끝 인덱스 까지 반전 범위에 적용이 안된다. 그래서 마지막에 +1을 해주어 전체 범위로 적용하는것.

동적 배열

c/c++에서 사용자가 입력한 값으로 배열의 크기를 지정할 수 없다.
그래서 정적으로 배열의 크기를 크게 해서 사용하는 식으로 해결했는데 이러면 메모리 낭비가 너무 심하니 동적으로 배열을 만들어 줬다.

바구니 초기화

문제에서 모든 바구니에 공이 들어있고 번호가 적힌 공의 번호가 바구니의 번호와 같아야 하니 저렇게 초기화 시켰다.

Haribo