[PS] 2014 Daejeon 6899 Permutation Cycles

숫자들의 순환 문제이다.

3 2 7 8 1 4 5 8 라는 숫자 배열이 들어오면 순서대로 번호가 붙는다.

3은 1번째, 2는 2번째

1 2 3 4 5 6 7 8
3 2 7 8 1 4 5 6

번호->값 의 순으로 읽는다 그러면

1->3->7->5->1

2->2

4->8->6

과 같이 3개의 순환고리가 생성되므로 답은 3이다.

본 문제를 풀기위해 처음 생각한 솔루션은

순서대로 읽어나가면서 배열에 값을 추가해, 고리를 모두 완성하는 방식이였다.

[1,3] 을 배열에 넣고 다음 첨자와 값이 2,2 인데 이 숫자들은 앞의 배열에 없으므로 새

배열을 생성한다. 따라서 다음과 같이 된다.

[1,3]
[2]                  //중복은 제외한다.

이제 그 다음 3,7을 넣는데 3이라는 숫자가 처음 배열에 있으므로 중복되지 않은

7을 추가한다.

[1,3,7]
[2]

이런식으로 배열을 순환하면 답이 구해지는데,

이방식은 추가적인 메모리를 사용한다 (공간복잡도 2n)

따라서 정확한 솔루션은

값을 첨자로 사용해 순환이 될때까지 반복을 하는것이다.

이 방법이 모든 첨자를 지나게되면 답을 구할수 있다.

↓
1 2 3 4 5 6 7 8
3 2 7 8 1 4 5 6

첫번째의 첨자는1 값은3이다. 그럼 3번째 첨자로 이동을한다, 1번쨰 첨자는 사용하였으니

앞으로 쓰지않을 값을 x 표시후 3으로 이동한다.

    ↓
1 2 3 4 5 6 7 8
x 2 7 8 1 4 5 6

첨자는 3이고 값은 7이므로 7번째로 이동후 값을 x 표시한다.

            ↓
1 2 3 4 5 6 7 8
x 2 x 8 1 4 5 6

첨자는 7이고 값은 5이므로 앞과 같은방식으로 진행한다.

        ↓      
1 2 3 4 5 6 7 8
x 2 x 8 1 4 x 6

이제 첨자는 5인데 값이 1이다. 시작 첨자와 현재 값이 같으므로 순환이 끝난다.

이제 사용하지않은 값은 x표시가 되어있으므로 사용하지 않은 첨자를 찾아 똑같은 솔루션

을 계속 적용하여 모든 첨자가 사용될때 까지 반복하면 답을 구할수 있다.