백준 2668 숫자고르기[JAVA]

🔗링크

2668 숫자고르기 Gold5

⚠️문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

🔍분석

---

각 배열의 숫자들이 사이클을 이루는지 확인하는 문제이다. 위의 예제로 따져보면 1-3 3-1로 연결되어 있는데 인덱스와 밸류의 집합이 동일하려면 사이클이 존재할 때까지 계속 밸류(3) -> 인덱스 검색(1), 검색된 밸류(3) -> 인덱스 검색(1) 반복하다 보면 사이클이 생긴다. 해당 사이클을 추출해내는 것이 주요 포인트였다.

---

1. 변수 선언은 아래 코드와 같이 하였다. N의 값, 배열을 저장할 arr배열, 방문했는지를 표시할 visited배열, 사이클이 존재할 경우 해당숫자가 사이클에 포함되었는지 확인할 cycle배열, 결과를 출력할 때 쓸 result 큐를 생성했다.

    static int N;
    static int[] arr;
    static boolean[] visited;
    static boolean[] cycle;
    static Queue<Integer> result = new LinkedList();

2.N의  값과 배열들을 초기화해주고 arr배열을 입력받는다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        arr = new int[N + 1];
        visited = new boolean[N + 1];
        cycle = new boolean[N + 1];

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

 

3.사이클을 체크할 큐를 생성한다. 사이클이 존재하거나, 이미 방문했던 숫자일 경우 때까지, 인덱스-배열[밸류1]-배열[밸류2] 의 형식으로 계속 검색하고 큐에 추가해준다. 사이클이 생겼더라도 큐에는 전체 숫자들이 사이클에 포함되는 것은 아니다. 사이클이 시작된 번호까지 큐에서 자르고 사이클이 시작된 번호부터 결과 사이클 배열에 포함시켜준다.

 

        for (int i = 1; i <= N; i++) {

            if(!visited[i]) {
                Queue<Integer> q = new LinkedList<>();

                q.add(i);

                int number = arr[i];

                while(!visited[number]) {
                    q.add(number);
                    visited[number] = true;
                    number = arr[number];
                }

                if (q.contains(number)) {
                    while(q.peek() != number) {
                        q.poll();
                    }

                    while (!q.isEmpty()) {
                        cycle[q.poll()] = true;
                    }

                }
             }
        }

✔전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    static int N;
    static int[] arr;
    static boolean[] visited;
    static boolean[] cycle;
    static Queue<Integer> result = new LinkedList();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        arr = new int[N + 1];
        visited = new boolean[N + 1];
        cycle = new boolean[N + 1];

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

        for (int i = 1; i <= N; i++) {

            if(!visited[i]) {
                Queue<Integer> q = new LinkedList<>();

                q.add(i);

                int number = arr[i];

                while(!visited[number]) {
                    q.add(number);
                    visited[number] = true;
                    number = arr[number];
                }

                if (q.contains(number)) {
                    while(q.peek() != number) {
                        q.poll();
                    }

                    while (!q.isEmpty()) {
                        cycle[q.poll()] = true;
                    }

                }
             }
        }

        for (int i = 1; i <= N; i++) {
            if(cycle[i]){
                result.offer(i);
            }
        }

        System.out.println(result.size());

        while (!result.isEmpty()) {
            System.out.println(result.poll());
        }
    }
}

😄결과