[백준] 1920번 : 수 찾기 – JAVA [자바]

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

1920번: 수 찾기

 

---

• 문제

 

 

---

• 문제 풀이

백준 1920번 수 찾기는 실버 4 난이도의 정렬 및 이분 탐색 문제이다.

 

이 문제에서는 N개의 정수들이 주어지고 그다음에 M개의 정수들이 주어진다. 이 M개의 정수들 중에서 전에 주어진 수면 1을 출력하고 이전에 주어진 수가 아니면 0을 출력하면 된다.

 

이 문제는 HashSet을 이용해서 풀 수도 있겠지만 이 풀이에서는 정렬과 이분 탐색을 해서 풀도록 하겠다.

 

우선 N개의 정수를 배열에 입력받고 오름차순 또는 내림차순으로 정렬을 해준다. 여기서 정렬이 중요하다. 정렬을 하지 않으면 이분 탐색을 이용해서 수를 찾을 수 없기 때문이다.

 

일반적인 배열을 순회하면서 찾는 건 O(N)의 시간복잡도를 가지고 있기 때문에 이분 탐색을 이용해 준다 (이분 탐색의 시간복잡도는 O(log N)이다). 

 

정렬을 하고 이분 탐색을 찾는 알고리즘의 총 시간복잡도는 O(N log N)이고, 일반적인 배열 순회로 찾는 알고리즘의 총 시간복잡도는 O(N^2)이므로 이분 탐색을 해준다.

 

Arrays.binarySearch() 함수는 만약에 찾지 못 했을 경우에는 음수를 반환한다. 따라서, 음수가 반환되면 0을 출력, 아니면 1을 출력해 주면 된다.

 

자세한 코드는 아래에 있는 코드를 참고해주면 되겠다.

 

---

• 코드

 

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

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

        // N 입력 받음
        int n = Integer.parseInt(br.readLine());

        // N개의 정수 배열을 입력 받음
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // N개의 정수 배열을 오름차순으로 정렬
        Arrays.sort(arr);

        // M 입력 받음
        int m = Integer.parseInt(br.readLine());

        // 결과를 저장하는 StringBuilder
        StringBuilder sb = new StringBuilder();

        // M개의 수들을 입력 받고, 이 수들이 N개의 정수 배열에 존재하는지 확인하여 결과를 StringBuilder에 추가
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());

            // 이진 탐색으로 M개의 수가 N개의 정수 배열에 존재하는지 확인
            int in = Arrays.binarySearch(arr, num);

            if (in < 0) {
                sb.append(0 + "\n"); // 존재하지 않으면 0을 StringBuilder에 추가
            } else {
                sb.append(1 + "\n"); // 존재하면 1을 StringBuilder에 추가
            }
        }

        // 최종 결과 출력
        System.out.println(sb);
    }
}