[1764] 듣보잡

난이도: ★★☆☆☆ • solved on: 2026-01-01

---

문제 요약

• 문제 유형: 해시 (Hash), 문자열, 정렬
• 요구사항: 듣도 못한 사람과 보도 못한 사람의 교집합을 찾아 사전식(오름차순)으로 출력해야 한다.

---

사용 개념

1. 자료구조

   • HashMap<String, Integer> / HashSet<String>
   • ArrayList<String> : 교집합 결과 저장
   • Collections.sort() : 사전식 정렬

2. 알고리즘/기법

   • 해시를 이용한 중복/존재 여부 체크
   • 교집합 추출 후 정렬

3. 핵심 키워드

   • 교집합 (intersection)
   • 사전식 정렬 (lexicographical order)

---

풀이 아이디어 및 코드

방법 1 : HashMap 카운팅으로 교집합 판별

1. 문제 분해

• 듣도 못한 사람 N명을 map에 넣고 값 1로 기록한다.
• 보도 못한 사람 M명을 입력받아 map.getOrDefault(name, 0) + 1로 누적한다.
• 최종적으로 값이 2인 키가 교집합(듣보잡)이므로 리스트에 담는다.
• 리스트를 사전식으로 정렬한 뒤 개수와 이름들을 출력한다.

2. 핵심 로직 흐름

   map에 N명은 1로 저장
   M명을 읽으며 map[name] += 1
   map 전체 순회하며 value==2인 key만 list에 저장
   list 정렬 후 출력

3. 예외 처리

   • 교집합이 0명일 수도 있으므로, 출력 형식을 그대로 유지한다.

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n =  Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        HashMap<String, Integer> map = new HashMap<>();
        int total = 0;
        StringBuilder sb = new StringBuilder();
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < n; i++){
            map.put(br.readLine(), 1);
        }

        for(int i = 0; i < m; i++){
            String name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        for(String key : map.keySet()){
            if(map.get(key)==2){
                total++;
                list.add(key);
            }
        }
        System.out.println(total);

        Collections.sort(list);

        for(int i = 0; i < list.size(); i++){
            sb.append(list.get(i)).append("\n");
        }

        System.out.println(sb);

    }
}

---

방법 2 : HashSet으로 존재 확인 후 교집합만 수집

1. 개선 포인트

• HashMap으로 전체를 카운팅하지 않고, 듣도 목록을 Set에 저장한 뒤
  보도 입력을 읽으면서 set.contains(name)인 경우만 결과 리스트에 추가한다.
• 교집합 후보만 모으므로, 불필요한 map.keySet() 전체 순회가 사라지고 코드가 더 단순해진다.

2. 핵심 로직 흐름

   set에 N명 저장
   M명을 읽으며 set에 있으면 result에 추가
   result 정렬 후 출력

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

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());

        HashSet<String> heard = new HashSet<>(n * 2);
        ArrayList<String> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            heard.add(br.readLine());
        }

        for (int i = 0; i < m; i++) {
            String name = br.readLine();
            if (heard.contains(name)) {
                result.add(name);
            }
        }

        Collections.sort(result);

        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append('\n');
        for (String name : result) sb.append(name).append('\n');
        System.out.print(sb);
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M + K log K)
  (K = 교집합 크기, 정렬 비용)
• 공간 복잡도: O(N + M) 수준 (map에 둘 다 들어갈 수 있음)

방법 2

• 시간 복잡도: O(N + M + K log K)
• 공간 복잡도: O(N + K) (듣도 set + 결과만 보관)

---

어려웠던 점

• 처음에는 HashMap으로 false/true 판별 방식도 고려했지만, 사전식 정렬을 해야 해서 결국 카운팅 방식으로 저장한뒤 정렬 로직을 따로 구성했다.
• Set.contains(value)는 평균적으로 O(1)인 것을 까먹었다

---

배운 점 및 팁

• 교집합 문제는 “한 쪽을 Set에 넣고, 다른 쪽을 보면서 contains로 걸러내기”가 가장 단순한 정석 패턴이다.
• 사전식 정렬은 결과 리스트만 정렬하면 되므로, 전체 자료구조를 정렬형(TreeSet)으로 유지할 필요는 보통 없다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1764
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 10816번 숫자 카드 2

• 확장 문제 (GPT 추천):

  • 백준 - 1764번 듣보잡 (정렬 대신 출력 포맷/자료구조 변형 연습)
  • HackerRank - Hash Tables: Ransom Note