백준 1764 듣보잡 ( Java )

 

안녕하세요 besforyou입니다

 

이번 글에서는 백준 문제 1764 풀이를 소개하겠습니다

---

문제 풀이

 

듣도 못한 사람의 이름 N개와 보도 못한 사람의 이름 M개 중 같은 이름의 개수와 같은 이름들을 사전순으로 출력하는 문제이다. N, M 값이 최대 500,000이 될 수 있으므로 순차 탐색 알고리즘을 쓰면 제한 시간안에 풀지 못한다. 그러므로 해쉬 맵을 사용하여 계산 시간을 줄여보자.

 

풀이 과정

1. N개의 듣도 못한 사람의 이름을 해쉬 맵에 저장한다.
2. 듣지도, 보지도 못한 사람의 이름을 저장할 ArrayList를 생성한다.
3. M개의 보도 못한 이름을 하나씩 읽으며 해쉬맵에 해당 이름이 존재하는지 탐색한다.
4. 보도 못한 이름이 해쉬 맵 안에 존재하면 ArrayList에 push
5. Collections.sort() 함수로 ArrayList를 사전순으로 정렬
6. ArrayList의 길이 + ArrayList의 모든 원소 출력

---

코드

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
 
public class Main {
    static int N, M;
    public static void main(String [] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
 
        Map<String, Integer> map = new HashMap<String , Integer>(N);
        ArrayList<String> ans = new ArrayList<String>();
 
        for ( int i = 0 ; i < N ; i++ ) {
            String name = br.readLine();
            map.put(name, 1);
        }
 
        StringBuilder sb = new StringBuilder();
        for ( int i = 0 ; i < M ; i++ ) {
            String name = br.readLine();
            if (map.containsKey(name)) {
                ans.add(name);
            }
        }
        Collections.sort(ans);
        for ( int i = 0 ; i < ans.size() ; i++ ) {
            sb.append(ans.get(i) + "\n");
        }
 
 
        System.out.println(ans.size());
        System.out.print(sb);
 
    }
}
 

 

---

결과