BOJ_2487_섞기 수열 (Java)

[Gold IV] 섞기 수열 - 2487

문제 링크

성능 요약

메모리: 17116 KB, 시간: 160 ms

분류

유클리드 호제법, 수학, 정수론, 순열 사이클 분할

제출 일자

2025년 2월 9일 13:38:15

문제 설명

A₁, A₂, …, A_N으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 카드에서 섞기 수열의 각 숫자가 나타내는 위치에 있는 카드를 순서대로 뽑아서 나열하는 것이다. 예를 들어, N = 6이고 섞기 수열이 [3, 2, 5, 6, 1, 4]라고 하자. 카드의 처음 상태가 [A₁, A₂, A₃, A₄, A₅, A₆]일 때, 섞기를 한 번 실행하면 카드의 순서가 다음과 같이 된다.

[A₃, A₂, A₅, A₆, A₁, A₄]

이 상태에서 다시 한 번 섞기를 실행하면 카드의 순서가 [A₅, A₂, A₁, A₄, A₃, A₆]이 되고, 다시 한 번 더 섞기를 실행하면 카드의 순서가 [A₁, A₂, A₃, A₆, A₅, A₄]가 된다. 이렇게 섞기를 반복하면 카드의 순서가 처음 상태인 [A₁, A₂, A₃, A₄, A₅, A₆]이 된다. 처음 상태로 돌아 올 때까지 반복한 섞기의 최소 횟수를 주어진 섞기 수열의 궤적이라 한다. 임의의 섞기 수열이 주어졌을 때, 그 섞기 수열의 궤적을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 카드의 수 N이 주어진다. N은 1 이상 20,000 이하의 수이다. 두 번째 줄에 섞기 수열을 나타내는 N 개의 자연수가 빈칸을 사이에 두고 주어진다.

출력

첫 번째 줄에 입력으로 주어진 섞기 수열의 궤적을 출력한다. 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.

문제 풀이

각 위치마다 사이클이 있는데 이 사이클의 최소공배수를 구하면 된다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N;
    static int[] arr;
    static boolean[] visited;
    static int res = 1;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2487_섞기수열/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        visited = new boolean[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                int len = 0;
                for (int j = i; !visited[j]; j = arr[j]) {
                    visited[j] = true;
                    len++;
                }
                res = LCM(res, len);
            }
        }

        System.out.println(res);
        bw.flush();
        bw.close();
        br.close();
    }

    private static int GCD(int a, int b){
        while(b != 0){
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    private static int LCM(int a, int b){
        return a / GCD(a, b) * b;
    }
}