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

문제를 이해하는데 시간이 걸렸던 것 같다. 

내가 이해한 바로,

1 2 3 4 5

2 3 5 4 1  

마치 쌍을 정해둔 것처럼 1 -> 2, 2 -> 3, 3 -> 5, 5 -> 1(원점으로 돌아오면 한 싸이클) , 4 -> 4 이렇게 총 2개의 싸이클이 형성된다는 것이다.

문제를 이해한 후에는 dfs 방식, while문을 써서 풀었고, 처음에 시간 초과가 떠서 BufferedReader로 입력 방식을 수정했더니 해결했다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int total = 0, N = 0;
        int[] array;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        total = Integer.parseInt(br.readLine());
        StringTokenizer st = null;

        for(int i = 1; i <= total; i++) {
            N = Integer.parseInt(br.readLine());
            array = new int[N+1];
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                array[j+1] = Integer.parseInt(st.nextToken());
            }
            System.out.println(solution(array, N));
        }
    }

    public static int solution(int[] array, int N) {
        int cycle = 0;
        boolean[] visited = new boolean[N+1];
        for(int i = 1; i <= N; i++) {
            if(!visited[i] && i != array[i]) {
                visited[i] = true;
                int j = array[i];
                while(i != array[j]) {
                    visited[j] = true;
                    j = array[j];
                }
                visited[j] = true;
                cycle++;
            } else if(!visited[i] && i == array[i]) {
                visited[i] = true;
                cycle++;
            }
        }
        return cycle;
    }
}

 

# Scanner 대신 BufferedReader!

scanner는 bufferedreader에 비해 읽어오는 속도가 느리기에 코딩테스트와 같은 시험에서는 bufferedreader를 쓰는 것이 속도 측면에서 유리하다고 한다!