BOJ_3182 : 한동이는 공부가 하기 싫어!

👉 문제링크

3182번: 한동이는 공부가 하기 싫어!

---

---

🔸 문제 분석 🔸

• n과 n개의 숫자를 입력받는다.
  • 숫자는 다음 숫자의 인덱스 번호를 가리킨다.
• 몇 번째 숫자 인덱스에서 시작해야 가장 많은 숫자를 걸치는지 출력한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        int max = -1, answer = -1;
        for (int i = 0; i < n; i++) {
            boolean[] visit = new boolean[n];
            int idx = i;
            int count = 0;
            while (!visit[idx]) {
                count++;
                visit[idx] = true;
                idx = arr[idx]-1;
            }
            if (count > max) {
                max = count;
                answer = i+1;
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• 숫자 배열의 각 인덱스에서 모두 실행해서 몇 개의 숫자를 걸쳐가는지 카운트한다.
  • 카운트 횟수의 최대값일때의 시작 인덱스를 출력한다.

---

🔸 end 🔸

• 최대값을 찾아야 해서 브루트포스 알고리즘을 직감했다.