[java/백준] 1764번 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

 

package 백준.정렬;
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Arrays;

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


        String[] st1=new String[N];
        ArrayList<String> list=new ArrayList<String>();

        for (int i=0;i<N;i++){
            st1[i]=br.readLine();
        }

        Arrays.sort(st1);

        for (int i=0;i<M;i++){
            String st2=br.readLine();
            for (int j=0;j<N;j++)
            {
                if (st2.equals(st1[j]))
                    list.add(st2);
            }

        }

        System.out.println(list.size());

        for (String s:list){
            System.out.println(s);
        }

    }

}

 

for문으로 풀었더니 시간초과가 떴다 .. 

모르겠어서 구글링 해보니 Hashset<>을 사용해야 하는 것 같다

 

 

 

Hashset의 특징

1. 중복을 허용하지 않으며 하나의 null 값 저장 가능

2. 순서대로 저장되지 않는다.

package 백준.정렬;
import java.io.*;
import java.util.*;

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


        String[] str=new String[N];
        ArrayList<String> list=new ArrayList<String>();
        HashSet<String> stringHashSet=new HashSet<>();

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

        for (int i=0;i<M;i++){
            String s=br.readLine();
            if(stringHashSet.contains(s))
                list.add(s);
        }

        Collections.sort(list);
        System.out.println(list.size());

        for (int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }

    }

}

 

 

https://www.acmicpc.net/problem/1764

1764번: 듣보잡