[백준/JAVA] 해시를 사용한 집합과 맵 1764 듣보잡

나의 답) 300ms

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());
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        HashMap<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            String name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }
        for (int i = 0; i < m; i++) {
            String name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }
        
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() >= 2) res.add(entry.getKey());
        }
        
        Collections.sort(res);
        
        sb.append(res.size()).append("\n");
        for (String name : res) {
            sb.append(name).append("\n");
        }
        
        System.out.print(sb);
    }
}

 

 

[코드 설명]

1. HashMap으로 등장 횟수 세기

• map.put(name, map.getOrDefault(name, 0) + 1)를 통해 이름의 등장 횟수를 세었다.
• "듣도 못한 사람"과 "보도 못한 사람"을 동일한 방식으로 처리해 간결성을 유지했다.

2. 등장 횟수가 2 이상인 경우 필터링

• map.entrySet()을 순회하면서 등장 횟수가 2 이상인 이름만 결과 리스트에 추가했다.

3. 사전순 정렬

• Collections.sort()를 사용해 결과 리스트를 사전순으로 정렬했다.

 

 

[시간 복잡도 분석]

1. 입력 처리 및 등장 횟수 계산

• 듣도 못한 사람: O(N)
• 보도 못한 사람: O(M)

2. 결과 필터링

• map.entrySet() 순회: O(U) (U는 map에 저장된 고유 이름 수)

3. 사전순 정렬

• O(K log K) (K는 듣보잡의 수)

4. 최종 시간 복잡도

• O(N + M + U + K log K)