백준 1920 수 찾기 - JAVA

1920 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] arr;
 
    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());
        arr = new int[N];
        StringBuilder sb = new StringBuilder();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        } 
        Arrays.sort(arr);
        
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(isIn(num) + "\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
    }
    private static int isIn(int num) {
        int left = 0;
        int right = arr.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (num == arr[mid]) {
                return 1;
            } else if (num < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 0;
    }
}

 

알고리즘 설명

---

해당 문제는 이분탐색과 HashSet 두 가지로 문제 해결이 가능합니다. 하지만 문제의 단계가 이분 탐색인만큼 이분 탐색을 활용하여 문제를 풀어보았습니다.
이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 선형탐색의 시간복잡도는 O(n)이고, 이분탐색의 시간복잡도는 O(logn)으로 선형 탐색과 달리 배열 크기를 반씩 나누면서 찾기 때문에, 탐색 횟수는 “배열 크기의 로그”에 비례합니다.
 
해당 문제에서 사용한 이분탐색의 방법입니다.

1. 배열의 중간값을 찾는다.
2. 중간값이 찾고자 하는 값과 같으면 1을 반환한다.
3. 중간값이 찾고자 하는 값보다 크면 right의 값을 중간값에서 1을 뺀 수로 설정한다.
4. 중간값이 찾고자 하는 값보다 작으면 left의 값을 중간값에서 1을 더한 수로 설정한다.
5. 배열에서 값을 찾지 못하면 0을 반환한다.

 

코드 해석

---

N과 입력값들을 arr 배열에 입력하고 해당 배열을 오름차순으로 정렬합니다. M만큼 입력 받은 수들을 차례로 이분탐색 함수( isIn함수 )에 집어넣어 1 또는 0을 반환합니다.