[JAVA][Baekjoon] 1920번 수 찾기 🌟

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

📌 접근 방식

1️⃣ 이진 탐색 사용

• 배열 A를 정렬하여 이진 탐색의 전제 조건(정렬된 배열)을 충족.
• M개의 수를 각각 A에 대해 이진 탐색을 사용해 존재 여부를 확인.
• 이진 탐색의 시간 복잡도는 O(logN), 이를 M번 수행하므로 총 시간 복잡도는 O(MlogN).

[알고리즘] 이진 탐색(Binary Search)

 

 

✅ PASS CODE

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int []A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        st = new StringTokenizer(br.readLine());
        // M개의 수에 대해 A에서 존재 여부를 확인
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            boolean find = false; // 해당 수가 A에 존재하는지 여부
            int num = Integer.parseInt(st.nextToken());
            int start = 0;
            int end = A.length - 1;

            // 이진 탐색
            while (start <= end) {
                int midi = (start + end) / 2;
                int midA = A[midi];
                if (midA > num) {
                    end = midi - 1; // 왼쪽으로 탐색 범위 좁힘
                } else if (midA < num) {
                    start = midi + 1; // 오른쪽으로 탐색 범위 좁힘
                } else {
                    find = true; // 값 발견
                    break;
                }
            }
            if (find) {
                System.out.println("1"); // 존재
            } else {
                System.out.println("0"); // 존재하지 않음
            }
        }
    }
}

😊 느낀 점

이진 탐색을 활용하면서 데이터 탐색의 효율성을 느낄 수 있었다! 데이터를 절반씩 줄여 나가면서 원하는 값을 빠르게 찾을 수 있었어서 편했다. 이 과정을 통해 정렬의 중요성도 다시 한번 깨달았다. 이진 탐색은 정렬된 데이터에서만 작동하기 때문에, 입력 데이터를 먼저 정렬하는 것이 필수적이었다. 이진 탐색은 코드 자체가 직관적이어서 금방 이해하며 풀 수 있었다! 🔥