[Algorithm Study] 백준 1764

문제 출처 : https://www.acmicpc.net/problem/1764

문제 접근

처음에 문제를 접근했을 때는 듣도 못한 사람들, 보도 못한 사람들 각각의 배열을 선언하고 정렬한 후에 비교해가면서 값을 출력하는 방식을 했으나 시간초과가 발생했다. 아무래도 2중 for문이 들어가면 시간초과가 발생하는 것으로 예상되었고 hashmap을 활용해 듣도 못한 사람들을 hashmap에 저장했고 보도 못한 사람 사람들은 hashmap의 키에 포함되는지를 판별하며 문제를 해결했습니다.

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int answer = 0;
        int cnt = 0;
        ArrayList<String> answer_arr = new ArrayList<>();
        Map<String, Integer> arr = new HashMap<>();
        for(int i = 0; i < N; i++){
            arr.put(br.readLine(), cnt++);
        }
        for(int i = 0; i < M; i++){
            String check = br.readLine();
            if(arr.keySet().contains(check)){
                answer++;
                answer_arr.add(check);
            }
        }
        Collections.sort(answer_arr);
        System.out.println(answer);
        for(int i = 0; i < answer_arr.size(); i++){
            System.out.println(answer_arr.get(i));
        }
    }
}