[백준 : JAVA] 4158 CD

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(a==0&&b==0)break;

            int cnt = 0;
            HashSet<Integer> list = new HashSet<>();
            int[] arr = new int[a];
            for (int i = 0; i < a ; i++) {
                arr[i] = Integer.parseInt(br.readLine());
            }
            for (int i = 0; i < b; i++) {
                if (Arrays.binarySearch(arr,Integer.parseInt(br.readLine()))>=0) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }

    }
}​

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(a==0&&b==0)break;

            int cnt = 0;
            HashSet<Integer> list = new HashSet<>();
            for (int i = 0; i < a ; i++) {
                list.add(Integer.parseInt(br.readLine()));
            }
            for (int i = 0; i < b; i++) {
                if (list.contains(Integer.parseInt(br.readLine()))) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }

    }
}

 

맨처음엔 List를 이용해 입력값을 저장하였는데 시간초과가 계속 떠서 찾아보니 List의 contains 메소드의 실행 시간이 O(n)인 반면 set은 O(1)이었다. 따라서 contains 메소드가 주인 이번문제는 set을 사용해야했다. 그후 binarySearch 메소드도 이용해 봤는데 더 빨라졌다. binarySearch의 시간복잡도는 O(logn)인데 왜 더 빨라졌을까?

아직 binarySearch를 사용할때 왜 더 빨라지는지는 모르겠다.