단계별로 풀어보기 14 - 집합과 맵 : 듣보잡

문제번호 1764번

첫째 줄에 순서대로 듣도 못한 사람수 N, 보도 못한 사람 M이 주어진다.

둘째 줄부터 N번 동안 듣도 못한 사람의 이름이 입력되고, M번 동안 보도 못한 사람의 이름이 입력된다.

듣도 보도 못한 사람의 수를 출력하고 사전순으로 이름을 출력해야 한다.

 

답안 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class bj1764 {
    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> c = new HashSet<>();
        TreeSet<String> b = new TreeSet<>();


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

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++){
            String tmp = br.readLine();
            if(c.contains(tmp)){
                b.add(tmp);
            }
        }

        sb.append(b.size()).append('\n');

        for(String tmp : b){
            sb.append(tmp).append('\n');
        }

        System.out.println(sb);

    }
}

 

틀린 답안(첫 제출) :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.NavigableSet;
import java.util.StringTokenizer;
import java.util.TreeSet;

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

        TreeSet<String> b = new TreeSet<>();


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

        NavigableSet<String> a = b.descendingSet();

        StringBuilder sb = new StringBuilder();
        int sum = 0;
        for(int i = 0; i < M; i++){
            String tmp = br.readLine();
            if(a.contains(tmp)){
                sum++;
                sb.append(tmp).append('\n');
            }
        }

        sb.insert(0, sum + "\n" );

        System.out.println(sb);

    }
}

 

comment :

# 처음엔 TreeSet에 넣고 입력 순서대로 듣도 보도 못한 사람을 판단하여 StringBuilder에 넣는 알고리즘을 짰으나, 이는 출력할 때 사전 순서가 아닌 입력 순서대로 되기 때문에 틀린 알고리즘이다.

# HashSet을 통해 듣도 못한 사람들의 이름들을 저장하고, TreeSet을 이용하여 듣도 못한 사람 중 보도 못한 시람을 탐색하여 정렬하였다.