[코드트리] 카드 사이클 만들기 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/create-card-cycle?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

1 이상 N이하의 숫자가 겹치지 않게 정확히 N개의 순서가 주어지고, 바꿀 위치인 목표 순서가 주어집니다. 이때, 기존 순서에 있던 숫자가, 목표 순서에 있는 위치로 이동하는 것을 따라가게 되면 사이클이 만들어집니다. 만약 처음 주어지는 카드의 순서가 5 1 4 2 3이고, 목표 순서가 2 5 3 1 4 라 한다면 다음과 같이 사이클이 만들어지게 됩니다.

 

카드의 처음 순서와 목표 순서가 아래 그림과 같이 주어집니다.

 

처음 순서에서 목표 순서까지 카드가 바뀌려면, 카드 위치가 변경되어야 하는 사이클이 있습니다. 이 예제에서는 2개의 사이클이 다음 그림과 같이 생깁니다.

 

위 예제를 참고하여 사이클의 총 개수와 사이클 중 최대 사이클의 크기를 출력하는 프로그램을 작성해 보세요.

 

입력 예시

5
5
1
4
2
3
2
5
3
1
4

 

출력 예시

2 3

 

 

코드

첫 번째 줄에 정수 N이 주어집니다.

두 번째 줄부터 N개의 줄에 걸쳐 초기 숫자 카드의 순서가 한 개씩 주어집니다.

그 다음 줄부터는 N개의 줄에 걸쳐 목표 순서가 한 개씩 주어집니다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] first = new int[n]; // 초기 순서 배열
        int[] target = new int[n]; // 목표 순서 배열
        boolean[] visited = new boolean[n]; // 방문 배열
        int cycleCount = 0; // 사이클 총 개수
        int cycleSize = 0; // 최대 사이클의 크기

        // 초기 배열 담기
        for (int i = 0; i < n; i++) {
            first[i] = Integer.parseInt(br.readLine());
        }

        // 목표 순서 배열 담기
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            // 초기 순서 요소와 목표 순서 요소의 위치가 같은 경우 0으로 처리하기 위함
            if (first[i] != num) {
                target[i] = num;
            }
        }
        br.close();

        // 초기 순서 배열 순회
        for (int i = 0; i < n; i++) {
            // 방문하지 않았고, 목표 순서의 위치가 다른 경우
            if (!visited[i] && target[i] != 0) {
                int current = first[i]; // 현재 숫자
                cycleCount++; // 사이클 개수 증가
                int size = 0;
                int idx = 0;

                // idx가 n보다 작으면 반복
                while (idx < n) {
                    // idx 번째 배열에 방문하지 않으면서 현재 숫자가 idx 번째 목표 숫자와 같은 경우
                    if (!visited[idx] && current == target[idx]) {
                        visited[idx] = true; // 방문처리
                        size++; // 사이클 크기 증가
                        current = first[idx]; // 현재 숫자 변경
                        idx = 0; // 인덱스 초기화
                    } else { // 그 외 인덱스 증가
                        idx++;
                    }
                }

                // 최대 사이클 크기 변경
                cycleSize = Math.max(cycleSize, size);
            }
        }

        // 사이클이 없는 경우
        if (cycleCount == 0) {
            cycleSize = -1;
        }

        bw.write(cycleCount + " " + cycleSize);
        bw.flush();
        bw.close();
    }
}