[백준][Java] 2668번 숫자고르기

이게 초등부문제라는게 믿기지가 않는다.

index에 속한 값을 이용하여 또 다른 index로 넘어가는

개념을 알아야 하는데, num[i] -> num[num[i]] -> num[ num[ num[i] ] ] -> ...

이렇게 반복하여 rotation을 시켜주다가

'마지막으로 도착하는 index가 가진 값' 

'최초의 index'의 값과 같아야 한다.

이렇게 되면 지금까지 지나간 index들이 모두 하나의 고리처럼 연결되어

문제에서 요구하는 숫자들의 집합이 된다.

이를 위해서 주의해야 할점은 Visited라는 boolean배열을 통해

rotation을 하면서 들렀던 index를 체크해주는 것이 중요하다.

그렇지 않으면 무한재귀할 수 있다.

최종 목적지까지 도달하여 문제에서 요구하는 조건을 만족하면

rotation함수를 돌리면서 만든 temp 배열리스트를 이용하여 ( 그간 지나온 index 저장해놓은 것 )

최종멤버(finMem) 배열에 체크해둔다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; public class Main { static int[] num; static boolean[] visited; static boolean[] finMem; static int last; static ArrayList<Integer> temp = new ArrayList<Integer>(); static int res=0; 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()); num = new int[N+1]; visited = new boolean[N+1]; finMem = new boolean[N+1]; for(int i=1; i<=N; i++) { num[i]=Integer.parseInt(br.readLine()); } for(int i=1; i<=N; i++) { temp.clear(); last=i; // 마지막 값은 시작한 index여야함. rotation(i); // System.out.println(num[i]); } bw.write(Integer.toString(res)+"\n"); for(int i=1; i<finMem.length; i++) { if(finMem[i]) bw.write(Integer.toString(i)+"\n"); } bw.flush(); bw.close(); } public static void rotation (int i) { if(visited[i] || finMem[i]) return; visited[i]=true; temp.add(i); // 꼬리 물면서 index 추가 rotation(num[i]); visited[i]=false; // 꼬리 물어서 세트 만듬 if(num[i]==last) { for(int j=0; j<temp.size(); j++) { finMem[temp.get(j)]=true; res++; } } } }