문제집 1766 Java

 

1766번: 문제집

package 백준.자바.문제집_1766;

import java.io.*;
import java.util.*;

public class Main {
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] entry = new int[N+1];

        List<List<Integer>> arr = new ArrayList<>();

        for(int i = 0; i < N+1; i++)
            arr.add(new ArrayList<>());

        int M = Integer.parseInt(st.nextToken());

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr.get(a).add(b);
            entry[b]++;
        }

        PriorityQueue<Integer> q = new PriorityQueue<>();

        for(int i = 1; i < N+1; i++){
            if(entry[i] == 0) q.add(i);
        }

        StringBuilder sb = new StringBuilder();

        while(!q.isEmpty()){
            int index = q.poll();
            sb.append(index).append(" ");

            for(var k : arr.get(index)){
                entry[k]--;
                if(entry[k] == 0) q.add(k);
            }
        }
        System.out.println(sb);
    }


    public static void main(String[] args) throws Exception{
        new Main().solution();
    }
}

 

제출 결과 시간이 매우 느리다고 생각되어 다른 분들 풀이의 시간을 보니 500ms로 제 시간의 1/6수준밖에 되지 않았다.

 

이유가 무엇인가 알아보니.. LinkedList와 ArrayList의 차이였다.

 

처음엔 별 생각없이 LinkedList를 사용했는데

 

LinkedList는 데이터가 고리형태로 이어져 있어서 get 메서드를 쓰면 O(n)의 시간이 걸린다고 한다.

 

위 코드를 LinkedList로 사용할 경우 get 메서드로 O(n) 작업이 매우 많아져서 느려진 것이었고,

 

LinkedList를 ArrayList로 바꾸니 다시 빨라진 것을 확인할 수 있었다.