[JAVA] 백준 1764번: 듣보잡

백준

[JAVA] 백준 1764번: 듣보잡

스파게티 코더 2024. 7. 23. 13:42

문제

듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도+보도 못한 사람의 명단을 사전 순으로 출력하는 문제.

아이디어

해시맵에 "듣도 못한 사람"의 명단을 저장해두고, "보도 못한 사람"의 이름을 입력받을 때마다 "듣도 못한 사람" 명단에도 해당 이름이 존재하는지(듣보잡인지) 체크한다.
해시맵에 "보도 못한 사람"의 이름이 있는지 체크하고, 있으면(듣보잡이면) 리스트에 따로 저장해 정렬한 후 출력한다.
해시맵을 사용하는 이유는 빠른 탐색이 가능하고, getOrDefault 메서드를 제공하기 때문이다.

풀이

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Map<String, Integer> map = new HashMap<>();
        
        // 듣도 못한 사람의 이름 저장
        for(int i=0; i<N; i++) {
            map.put(br.readLine(), 1);
        }
        
        // 듣보잡 정렬을 위한 리스트 선언
        List<String> list = new ArrayList<>();
        
        // 보도 못한 사람의 이름 입력
        for(int i=0; i<M; i++) {
            String str = br.readLine();
            
            // 듣도 못한 사람이기도 한지 체크(듣보잡이냐)
            int num = map.getOrDefault(str, -1);
            
            // 듣보잡이 맞으면 리스트에 추가
            if(num > 0) {
                list.add(str);
            }
        }
        Collections.sort(list);

        sb.append(list.size()).append('\n');
        for(String str: list) {
            sb.append(str).append('\n');
        }
        System.out.println(sb);
    }
}

채점 결과

문제 링크

1764번: 듣보잡 (acmicpc.net)