박스 정렬
면접 대비시간 제한1초메모리 제한128 MB
배열을 오름차순으로 정렬하는 데 필요한 순환 이동 명령의 최소 개수를 지정된 사이클 분해 방식으로 구성하는 문제입니다.
문제
N개의 박스가 한 줄로 놓여 있다. 각 박스에는 1부터 N까지의 서로 다른 수가 하나씩 적혀 있으며, 왼쪽부터 오른쪽으로 수가 오름차순이 되도록 박스를 정렬하려고 한다.
로봇에게 내리는 명령은 서로 다른 위치들로 이루어진 수열이다. 명령이 p_1, p_2, ..., p_k라면, 현재 위치 p_i에 있는 박스는 모든 1 <= i < k에 대해 위치 p_{i+1}로 이동하고, 현재 위치 p_k에 있는 박스는 위치 p_1로 이동한다.
가능한 한 적은 수의 명령으로 박스를 정렬하는 프로그램을 작성하라.
입력
첫째 줄에 박스의 수 N이 주어진다 (2 <= N <= 1000).
다음 줄에는 현재 순서대로 박스에 적힌 N개의 서로 다른 정수가 주어진다.
출력
첫째 줄에 사용한 명령의 수 X를 출력한다.
그다음 X개의 줄에는 로봇에게 내린 명령을 순서대로 출력한다. 각 명령 줄에는 수열의 길이, 콜론(:), 공백 한 칸, 그리고 수열의 위치들을 공백으로 구분해 출력한다.
다음 표준 최적 구성을 사용한다. 위치를 1부터 N까지 차례로 확인한다. 아직 처리하지 않은 위치 i에 대해, 현재 위치 i에 있는 박스 번호를 A_i라고 할 때 i, A_i, A_{A_i}, ...처럼 사이클이 닫힐 때까지 따라간다. 길이가 1인 사이클은 출력하지 않는다. 길이가 2인 사이클은 발견한 순서의 반대로 출력하고, 길이가 3 이상인 사이클은 발견한 순서 그대로 출력한다.