[JAVA / 자바] 백준 1920번 - 수 찾기

문제

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을 출력한다.

---

 

---

문제 접근 방법

이번 문제는 첫 번째 입력으로 수의 집합이 주어지고, 두 번째 입력으로 검색할 수의 집합이 주어진다.

따라서 처음에 주어지는 수의 집합을 어떤 자료형에 저장해서 검색했을 때 성능이 좋을지를 판단하는 문제라고 볼 수 있다.

1. ArrayList + contains()

2. int [] + Arrays.sort() + Arrays.binarySearch()

3. HashSet + contains()

이제 위 세 가지의 함수를 사용한 코드를 작성하여 성능을 비교해 보려 한다.

---

JAVA 코드 풀이

1. ArrayList + contains()

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

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));
        int len = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<String> num = new ArrayList<>();
        while(len-- > 0)
            num.add(st.nextToken());
        len = Integer.parseInt(br.readLine());
        String isIn[] = br.readLine().split(" ");
        for(String i : isIn)
            bw.write(num.contains(i) ? "1\n" : "0\n");
        bw.close();
    }
}

2. int [] + Arrays.sort() + Arrays.binarySearch()

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

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));
        int len = Integer.parseInt(br.readLine());
        String num[] = br.readLine().split(" ");
        Arrays.sort(num);
        len = Integer.parseInt(br.readLine());
        String isIn[] = br.readLine().split(" ");
        for(int i=0; i<len; i++)
            bw.write(Arrays.binarySearch(num, isIn[i]) >= 0 ? "1\n" : "0\n");
        bw.close();
    }
}

3. HashSet + contains()

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

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));
        int len = Integer.parseInt(br.readLine());
        HashSet<Integer> list = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<len; i++)
            list.add(Integer.parseInt(st.nextToken()));
        len = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while(len-- > 0)
            bw.write(list.contains(Integer.parseInt(st.nextToken()))? "1\n" : "0\n");
        bw.close();
    }
}

코드 실행 결과

1. ArrayList + contains()

2. int[] + Arrays.sort() + Arrays.binarySearch()

3. HashSet + contains()

---

후기

처음 나는 ArrayList에 저장해서 contains() 함수를 사용해서 검색하려 했는데 시간 초과가 났다. 그래서 찾아보니 은근 contains() 함수의 연산 시간이 꽤 걸린다 해서 1차원 배열에 저장 후 정렬(Arrays.sort)하여 이분 검색(binarySearch())을 했더니 문제가 풀렸고, 어디선가 데이터 저장 검색 시 HashSet자료형이 연산 속도가 빠르다고 들은 것이 생각나서 코드를 작성해 봤더니 메모리는 리스트보다 사용하지만, 연산 속도는 더 빨랐다. 이번 문제처럼 저장 순서가 상관없고 중복입력이 없는 경우 자료 검색은 HashSet 자료형을 사용하면 보다 쉽고 편리하게 코드를 작성할 수 있을 것 같다.

---

문제 원본

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