(Java) 백준 1764 - 듣보잡

간단한 문제라고 생각했는데 의외로 20분이 넘게 걸렸다.

처음에 아무 생각 없이 ArrayList를 사용해서 각 list에 입력값을 넣어주고

2중 for문을 돌리며 비교했다가 4%에서 바로 시간 초과가 나왔다.

시간제한이 2초인데 왜 시간 초과가 나지? 하고 문제를 다시 보니

N과 M이 각각 500,000 이하의 자연수였다....

그래서 이중 for문을 없애고 retainAll을 사용해서 교집합을 구했지만

또 시간 초과... 생각해보니 List는 탐색 시간이 오래 걸린다는 단점이 생각이 났고

그때가 되어서야 set이 생각났다. 또 문제에 입력값이 중복이 없다 라는 힌트가 있었는데

눈치채지 못했었다.

정렬이 되는 TreeSet을 이용해서 문제를 풀어 맞았다. 그런데  다른 분들의 답을 보니

입력을 n만큼 HashSet으로 받고 m부터는 contain을 이용해서 Hashset에 값이 있는 경우에만

List에 추가해서 정렬 후 출력하는 방법도 있었다.

쉬운 문제였지만 여러 방법으로 생각할 수 있어서 좋았다.

 

최종 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        Set<String> dset = new TreeSet<>();
        Set<String> bset = new TreeSet<>();
        String[] d = new String[n];
        String[] b = new String[m];

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

        dset.retainAll(bset);

        sb.append(dset.size()).append("\n");
        for (String s : dset) {
            sb.append(s).append("\n");
        }
        System.out.println(sb);
    }
}