[BOJ/Java] 듣보잡 (1764)

듣보잡 (1764)

1. 문제 분석

문제 개요

• 듣도 못한 사람과 보도 못한 사람의 목록이 주어졌을 때, 두 목록에 모두 속하는 사람들을 찾아 사전순으로 출력하는 문제이다.

입력 형식

• 첫 줄에 듣도 못한 사람의 수 N과 보도 못한 사람의 수 M이 주어진다.
• 다음 N개의 줄에 듣도 못한 사람의 이름이 주어지고, 이후 M개의 줄에 보도 못한 사람의 이름이 주어진다.

출력 형식

• 듣도 보도 못한 사람의 수와 그들의 이름을 사전순으로 출력한다.

2. 알고리즘 종류

이 문제를 해결하기 위해 사용할 수 있는 알고리즘은 다음과 같다:

• 해시맵(HashMap): 해시맵을 사용하여 각 이름이 몇 번 등장했는지를 효율적으로 기록하고, 이를 통해 중복된 이름을 쉽게 찾을 수 있다.
• 정렬 알고리즘(Sorting): 최종적으로 중복된 이름들을 사전순으로 정렬하여 출력한다.

3. 주요 부분 및 코드 작성 방법

1. 입력 처리
   • BufferedReader를 사용하여 입력을 효율적으로 처리한다.
   • StringTokenizer를 사용해 첫 줄에서 N과 M을 분리하여 읽어온다.
2. 이름 중복 체크
   • HashMap을 사용하여 각 이름의 등장 횟수를 기록한다.
   • 중복되지 않은 이름은 리스트에 추가하고, 중복된 이름만을 추려낸다.
3. 사전순 정렬
   • 중복된 이름들을 리스트에 저장한 후, Collections.sort()를 사용해 사전순으로 정렬한다.
4. 결과 출력
   • 듣도 보도 못한 사람의 수를 출력하고, 중복된 이름들을 순서대로 출력한다.

4. 코드 설명

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 줄에서 N과 M 값을 읽어온다
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 이름을 저장할 해시맵을 선언
        Map<String, Integer> map = new HashMap<>();
        // 중복되지 않은 이름을 저장할 리스트를 선언
        List<String> names = new ArrayList<>();

        // N + M 번 반복하며 이름을 입력받는다
        for(int i = 0; i < N + M; i++) { 
            String n = br.readLine();
            // 해시맵에 이름이 없으면 리스트에 추가하고 중복 여부 체크
            if(!map.containsKey(n)) names.add(n);
            // 해시맵에 이름을 키로 하여 등장 횟수를 값으로 저장
            map.put(n, map.getOrDefault(n, 0) + 1); 
        }

        // 중복되지 않은 이름 리스트를 사전순으로 정렬
        Collections.sort(names);

        // 듣도 보도 못한 사람의 수를 출력
        System.out.println((N + M) - names.size());
        // 중복된 사람들만 출력
        for(String s : names) {
            if(map.get(s) != 1) System.out.println(s);
        }
    }
}

5. 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 줄에서 N과 M 값을 읽어온다
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 이름을 저장할 해시맵을 선언
        Map<String, Integer> map = new HashMap<>();
        // 중복되지 않은 이름을 저장할 리스트를 선언
        List<String> names = new ArrayList<>();

        // N + M 번 반복하며 이름을 입력받는다
        for(int i = 0; i < N + M; i++) { 
            String n = br.readLine();
            // 해시맵에 이름이 없으면 리스트에 추가하고 중복 여부 체크
            if(!map.containsKey(n)) names.add(n);
            // 해시맵에 이름을 키로 하여 등장 횟수를 값으로 저장
            map.put(n, map.getOrDefault(n, 0) + 1); 
        }

        // 중복되지 않은 이름 리스트를 사전순으로 정렬
        Collections.sort(names);

        // 듣도 보도 못한 사람의 수를 출력
        System.out.println((N + M) - names.size());
        // 중복된 사람들만 출력
        for(String s : names) {
            if(map.get(s) != 1) System.out.println(s);
        }
    }
}