<Algorithm> 81. 1764번 듣보잡

1. 1764번 듣보잡

• 문자열 문제, 푸는 방법이 여러개가 있을 것 같았다. 처음에 단순히 모두 비교를 했는데 시간초과가 나왔다.

• 500000가 모두 4999900까지 같고 뒤에만 다르면 500000*500000을 해야되는데 처음부터 문제를 정독하는 것이 중요한 것 같다.

• 바이너리서치를 생각하지 못한 것은 아직 많이 부족하다는 걸 다시 느끼게 되었다.

• 이 문제는 Map을 활용할 수 있는지에 대한 것이라고 생각된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/*
 * 바이너리 서치
 * 다넣고 중복되는거 찾기
 * Map 쓰기
 * 
 */
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Map<String, Integer> map = new HashMap<String, Integer>();
        PriorityQueue<String> pq = new PriorityQueue<>();
        ArrayList<String> ans = new ArrayList<>();
        
        for(int i = 0; i < N ; i++) {
            map.put(br.readLine(),0);
        }
        
        for(int i = 0; i < M ; i++) {
            String str = br.readLine();
            if(map.get(str) ==null) {
            }else {
                pq.add(str);            
            }
        }        
        
        
        System.out.println(pq.size());
        while(!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
    
}
 
/*import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String[] no = new String[N];
        String[] list = new String[M];
        ArrayList<String> ans = new ArrayList<>();
        
        for(int i = 0; i < N ; i++) {
            no[i] = br.readLine();
        }
        
        for(int i = 0; i < M ; i++) {
            list[i] = br.readLine();
        }        
        
        Arrays.sort(no);
        Arrays.sort(list);
        
        
        for(int i = 0; i < M;i++) {
            if(Arrays.binarySearch(no,list[i])>=0) {
                ans.add(list[i]);
            }
        }
        
        
        System.out.println(ans.size());
        for(int i = 0 ; i < ans.size(); i++) {
            System.out.println(ans.get(i));
        }
    }
    
}
*/

참고 & 출처