[P&B] #76 BAEKJOON 1920

백준 1920번 수 찾기 JAVA

문제 설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

나의 문제 풀이 코드

import java.util.*;
import java.io.*;
public class bj1920 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String[] A = br.readLine().split(" ");

        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(A[i]);
        }

        int M = Integer.parseInt(br.readLine());
        String[] B = br.readLine().split(" ");

        for (int i = 0; i < M; i++) {
            if (set.contains(B[i]))
                bw.write("1\n");
            else
                bw.write("0\n");
        }
        bw.flush();
    }
}

 

문제 풀이 코멘트

처음에는 아래의 코드로 문제를 풀었습니다.

String N = br.readLine();
String A = br.readLine();

int M = Integer.parseInt(br.readLine());
String[] B = br.readLine().split(" ");
for (int i = 0; i < M; i++) {
   if (A.toString().contains(B[i]))
      bw.write("1\n");
   else
      bw.write("0\n");
}

하지만 자꾸 시간초과가 발생했고 질문게시판을 보니 contains() 함수가 문제가 되었을 수도 있겠다는 생각을 하게 되었습니다.

contains()는 리스트의 크기에 비례하는 O(n)의 시간복잡도를 갖습니다. 따라서 입력의 최대치인 N = M = 100,000인 경우에 반복문을 통해 contains()로 존재 여부를 확인하면 최대 100억번의 연산이 필요하기 때문에 시간초과가 발생할 수밖에 없습니다.

존재여부만 알아내면 되니까 HashSet과 해당 컬렉션의 contains 메소드 사용해보는 것이 하나의 방법이라고 하여 그렇게 수정을 했고 시간초과가 되지 않고 풀 수 있었습니다. 물론 set보다는 이분탐색과 같은 다른 빠른 탐색방법이 존재하지만....(생략)