[백준/Java] 10451 순열 사이클

반응형

---

 

알고리즘은 너무 어렵다..

뒤 아래 순열을 비교하고 두 배열의 i번째 인덱스 값이 같으면 하나의 사이클로

다르면 방향 그래프로 나누고

Set을 이용하여 이미 확인한 인덱스를 식별한다.

 

처음 코드를 짰을 때 indexoutofexception 에러가 떠서 조건을 배열의 길이를 넘지 않게 수정해 주었다.

내가 짠 코드를 Scanner로 입력 값을 받는 코드로 바꾸는 것도 애를 먹었다ㅠㅠ

매일 노력해야겠다

 

//Scanner로 입력 값 누르기 싫어서 아래처럼
//입력값을 따로 파일을 만들어 
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //n = Integer.parseInt(br.readLine());
        //addNumber("");
		//br.close();
//이렇게 받아도 된다.

public class Main {
	public static void main(String args[]) {
    	
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] permutation = {2, 1, 3, 4, 5, 6, 7, 9, 10, 8};
        
        int cycle = 0;
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<permutation.length; i++) {
        	if(arr[i] == permutation[i]) {
            	cycle++;
            } else {
            	if(!set.contains(i)) {
                	int current = i;
                    while(!set.contains(current) && current >= 0 && current < n) {
                    	set.add(current);
                        current = permutation[current];
                    }
                    cycle++;
                }
            }
        }
        System.out.println(cycle);
    }
}

 

백준 제출 용

보통 boolean 배열로 인덱스 경로를 확인한다.

public class Main {
	public static void main(String args[]) {
    	Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        for(int i=0; i<T; i++) {
        	int N = sc.nextInt();
            int[] permutation = new int[N + 1];
            boolean[] visited = new boolean[N + 1];
            int cycle = 0;
            
            for(int i=1; i<=N; i++) {
            	permutation[i] = sc.nextInt();
            }
            
            for(int i=1; i<=N; i++) {
            	if(!visited[i]) {
                	int current = i;
                    while(!visited[current]) {
                    	visited[current] = true;
                        current = permutation[current];
                    }
                    cycle++;
                }
            }
            System.out.println(cycle);
        }
        sc.close();
    }
}