[자바] 백준 1764번 듣보잡

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

 

[문제 이해]

듣도 못한 사람의 수 N, 보도 못한 사람의 수 M을 각각 입력 받고 String 배열 N과 M에 모두 속하는 사람의 수와 이름을 찾아서 출력하면 되는 문제였다. 

 

[문제 풀이]

N만큼의 크기를 갖는 ArrayList와 M만큼의 크기를 갖는 ArrayList를 각각 만들어서 ArrayList에 있는 contains() 함수를 사용해서 함수 내에 있는 원소를 비교하면 될 줄 알았는데 시간 초과가 났다.. 찾아보니 HashSet의 contains() 함수를 사용해야 시간초과가 안난다고 해서 HashSet을 사용해서 문제를 풀었다.

 

• HashSet의 contains() = 시간복잡도 : O(1)
• ArrayList의 contains() = 시간복잡도 : O(n)

이러면 속도 차이가 날 수 밖에 .. 🥹 배열 문제도 좀 풀어보면서 감을 더 잡아야 될 것 같다 ..

 

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

public class Main {

    public static int sum = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        HashSet<String> n_hash = new HashSet<>();


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

        ArrayList<String> n_m = new ArrayList<>();

        for(int i = 0; i < m; i++){
            String m_arr = br.readLine();
            if(n_hash.contains(m_arr)){ // HashSet의 contains()의 시간 복잡도 = O(1)
                n_m.add(m_arr);
            }
        }

//        for(int i = 0; i < m; i++){
//            if(n_arr.contains(m_arr.get(i))){
//                n_m.add(m_arr.get(i)); // ArrayList의 contains()의 시간 복잡도 = O(n)
//            }
//        }

        n_m.sort(Comparator.naturalOrder());

        bw.write(String.valueOf(n_m.size())+"\n");

        for(int i = 0; i < n_m.size(); i++){
            bw.write(n_m.get(i) + "\n");
        }
        bw.flush();
        bw.close();
    }
}

 

ArrayList를 사전순으로 정렬하는 것도 Comparator.naturalOrder()를 통해 할 수 있다는 걸 알게 되었다. 원래 자주 사용하던 Arrays.sort()는 int[]을 정렬할 때 사용한다.