[C++] 백준 4단계 - 10811번 문제 (바구니 뒤집기)

문제설명

 

소스코드

#include <iostream>
using namespace std;
int main() {
	int N; int M;
	cin >> N >> M;
	int* arr = new int[N]; //동적 할당
	int a; int b;
	for (int i = 0; i < N; ++i) arr[i] = i + 1; //배열 초기화
	for (int i = 0; i < M; ++i)
	{
		cin >> a >> b;
		for (int j = 0; j <= (b - a) / 2; ++j)
		{
			int tmp = 0;
			tmp = arr[j + a - 1];
			arr[j + a - 1] = arr[b - j - 1];
			arr[b - j - 1] = tmp;
		}
	}
	for (int i = 0; i < N; ++i) cout << arr[i] << " ";
}

 

풀이

• 1부터 N까지 수 중에서 i부터 j까지의 수를 역순으로 M번 정렬한다.

내가 작성한 소스코드는 기본적으로 swap 알고리즘을 기초로 만들어졌다.

swap알고리즘의 내용 이전에 내가 작성한 https://rebugs.tistory.com/143 에서 확인할 수 있다.

[JAVA] 배열 요소를 역순으로 정렬하는 알고리즘

위 포스팅의 응용버전이 이번 문제인 것 같다.

자세한 스왑 과정을 확인하려면 아래와 같은 코드로 과정을 지켜보면 된다.

#include <iostream>
using namespace std;
int main() {
	int N; int M;
	cin >> N >> M;
	int* arr = new int[N];
	int a; int b;
	for (int i = 0; i < N; ++i) arr[i] = i + 1;
	for (int i = 0; i < M; ++i)
	{
		cin >> a >> b;
		for (int j = 0; j <= (b - a) / 2; ++j)
		{
			int tmp = 0;
			tmp = arr[j + a - 1];
			cout << arr[j + a - 1] << "와 " << arr[b - j - 1] << "를 바꿉니다." << endl;
			arr[j + a - 1] = arr[b - j - 1];
			arr[b - j - 1] = tmp;
		}
		for (int i = 0; i < N; ++i) cout << arr[i] << " ";
		cout << endl;
	}
	for (int i = 0; i < N; ++i) cout << arr[i] << " ";
}