[C++][swea] 20936 상자 정렬하기

20936 상자 정렬하기

공부 날짜 : 2024.07.20
정답 참조 여부 : X

문제 개요

1~N번의 상자 N개와 1~N+1칸의 보관함이 있다.
보관함의 1~N번까지 상자가 랜덤으로 배치되어 있을때, 특정 번호의 보관함을 선택하여 상자를 빈칸으로 옮기는 과정을 최대 1500번 시행하여 상자를 순서대로 정렬하는 문제이다.

나의 생각

가장 먼저 떠오른 생각은 순열 사이클
1~N번까지 상자가 순열중 하나의 모습으로 배치되어 있는 상태이다.
정렬을 위해 가장 간단한 방법은 한칸을 비우고(해당 칸에 있던 상자는 N+1번으로 간다.) 해당칸에 맞는 상자를 가져와 채워넣는과정을 반복하는것이다. 이는 사이클에 해당하며 하나의 사이클을 만족하면 가장 먼저 옮겼던(N+1번 보관함에 있는 상자)상자의 번호가 비어있게 된다.
이를 사이클 개수만큼 반복하면 정렬이 완료된다.

그래서 1번을 먼저 비우고 1번의 위치를 알기위해 상자의 번호를 인덱스 위치를 value로 저장해 주었고, 정렬여부를 체크하며 사이클 탐색을 한 결과 통과 되었다.

소스코드

#if 1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int N;
int arr[501];
bool check[501];
int answer[1500];
int count;
int target;

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);
	freopen("input_20936.txt", "r", stdin);

	int T;
	std::cin >> T;
	while (T--) {
		std::cin >> N;
		for (int i = 1; i <= N; i++) {
			int a;
			std::cin >> a;
			arr[a] = i;
			check[i] = false;
		}
		
		count = 0;
		for (int i = 1; i <= N; i++) {
			if (check[i]) continue;
			if (arr[i] == i) continue;
			check[i] = true;
			answer[count++] = i;
			target = arr[i];

			while (target != i) {
				answer[count++] = target;
				check[target] = true;
				target = arr[target];
			}

			answer[count++] = N + 1;
		}

		std::cout << count << "\n";
		for (int i = 0; i < count; i++) {
			std::cout << answer[i] << " ";
		}
		std::cout << "\n";
		

	}
}

#endif