[백준/JAVA] 1920

백준 1920번 문제

결과 코드

import java.io.*;
import java.util.HashSet;
import java.util.List;

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

        String N = br.readLine();
        String[] A = br.readLine().split(" ");
        String M = br.readLine();
        String[] strings = br.readLine().split(" ");

        HashSet hashSet = new HashSet<>(List.of(A));
        for (String s : strings) {
            if (hashSet.contains(s)) {
                bw.write(String.valueOf(1));
            } else {
                bw.write(String.valueOf(0));
            }
            bw.newLine();
        }
        bw.flush();
    }
}

---

개선 내용

HashSet을 사용해서 시간 복잡도를 O(logN)으로 줄였다.
아래는 실패했던 코드다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

        String N = br.readLine();
        String[] A = br.readLine().split(" ");
        String M = br.readLine();
        String[] strings = br.readLine().split(" ");

        List<String> arrayList = new ArrayList<>(Arrays.asList(A));

        for (String s : strings) {
            if (arrayList.contains(s)) {
                bw.write(String.valueOf(1));
            } else {
                bw.write(String.valueOf(0));
            }
            bw.newLine();
        }
        bw.flush();
    }
}

---

실패 요인

단순 ArrayList 에서 contains()를 사용해서 입력받은 값이 존재하는지 체크했었다.
하지만 시간 초과가 떴었고 원인을 찾아보니

contains()의 경우 존재 여부를 확인하기 위해 일일히 찾기 때문에
시간 복잡도 O(N)의 시간 복잡도를 갖는다는 것이였다.

이를 줄이기 위해서는 HashSet이라는 자료형을 사용하면 해결할 수 있다.