[백준] 1764: 듣보잡 JAVA

링크: https://www.acmicpc.net/problem/1764

---

풀이과정

이 문제는 이분탐색 or HashSet을 사용해서 푸는 문제이다.

 

이분탐색

이 문제에서 선형탐색을 한다면 O(NM) > 2초 (2억번의 연산)이 되어 이분탐색을 사용해야한다. 이분탐색의 시간복잡도는 O(log M)이되는데, 이걸 N번 반복하여 O(N logM)이 된다 (구현에 따라 O(M logN).

 

HashSet

자바에서 사용하는 자료구조로 요소간 중복이 불가하며, 빠른 탐색, 삽입, 삭제가 장점이다 {각각 평균적으로 O(1)}.

---

최종 코드

//이분탐색
import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String[] arrN = new String[N];
        String[] arrM = new String[M];
        for(int i = 0; i < N; i++){
            arrN[i] = br.readLine();
        }
        for(int i = 0; i < M; i++){
            arrM[i] = br.readLine();
        }
        int count = 0;
        Arrays.sort(arrN);
        Arrays.sort(arrM);
        ArrayList<String> answer = new ArrayList<>();
        for(int i = 0; i < M; i++){
            if(Arrays.binarySearch(arrN, arrM[i]) >= 0){
                count++;
                answer.add(arrM[i]);
            }
        }
        bw.write(count + "\n");
        for(int i = 0; i < answer.size(); i++){
            bw.write(answer.get(i) + "\n");
        }
        bw.flush();
    }
}

//HashSet
import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        HashSet<String> set = new HashSet<>();
        for(int i = 0; i < N; i++){
            set.add(br.readLine());
        }
        ArrayList<String> answer = new ArrayList<>();
        for(int i = 0; i< M; i++){
            String name = br.readLine();
            if(set.contains(name)){
               answer.add(name); 
            }
        }
        Collections.sort(answer);
        bw.write(answer.size()+"\n");
        for(int i = 0; i < answer.size(); i++){
            bw.write(answer.get(i)+"\n");
        }
        bw.flush();
    }
}