[ 백준 ] 1920번 수 찾기 (Java 자바)

🔗 문제 링크: 백준 1920번 - 수 찾기

문제 설명

 

주어진 문제는 수 찾기 문제로, N개의 정수로 이루어진 배열이 있을 때, 특정 정수 x가 배열 내에 존재하는지를 판별하는 문제이다.

이 문제는 이분 탐색(Binary Search) 기법을 활용하여 효율적으로 해결할 수 있다.

 

입력 조건

• 첫 번째 줄: 정수의 개수 N (배열의 크기)

• 두 번째 줄: N개의 정수가 공백으로 구분되어 주어진다.

• 세 번째 줄: 찾고자 하는 수의 개수 M

• 네 번째 줄: M개의 정수가 공백으로 구분되어 주어지며, 각각이 찾고자 하는 대상(target)이다.

 

---

풀이 과정

📌 문제 요약

• 배열 내에 주어진 target 값이 존재하는지 여부를 판별하는 문제

• 정렬된 배열에서 이분 탐색을 통해 target을 효율적으로 찾는다.

📌 해결 전략

1. 배열 정렬:

• 먼저 입력받은 배열을 오름차순으로 정렬한다.

2. 이분 탐색 수행:

• 각 target에 대해 이분 탐색을 진행한다.

• 탐색 시, left = 0, right = 배열의 마지막 인덱스로 설정하고,

while (left ≤ right) 동안 중간 값(mid)을 계산하여 target과 비교한다.

3. 결과 출력:

• target이 배열에 존재하면 1, 존재하지 않으면 0을 출력한다.

 

📌 풀이 과정 (이분 탐색)

1. 초기 설정:

• left = 0, right = arr.length - 1

2. 반복문 수행:

• while (left ≤ right) 반복문 내에서,

• mid = left + (right - left) / 2로 중간 인덱스를 구함.

• 만약 arr[mid]와 target이 같다면, 해당 target이 존재하므로 1을 반환.

• target이 arr[mid]보다 작다면, 오른쪽 경계를 mid - 1로 조정.

• target이 arr[mid]보다 크다면, 왼쪽 경계를 mid + 1로 조정.

3. 종료 조건:

• 반복문이 종료될 때까지 target을 찾지 못하면 배열 내에 존재하지 않으므로 0을 반환.

 

📌 시간 복잡도 분석

• 정렬: O(N log N)

• 이분 탐색: 각 검색마다 O(log N)이 소요되며, M번의 검색을 수행하므로 전체 탐색은 O(M log N)

• 따라서 전체 시간 복잡도는 배열 정렬과 이분 탐색을 합쳐 O(N log N + M log N)이다.

 

package BinarySearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

class BOJ_S4_1920 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 배열의 크기 N 입력 받기
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

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

        // 이분 탐색을 위해 배열 정렬
        Arrays.sort(arr);

        // 찾을 숫자의 개수 M 입력 받기
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());

        // 각 target에 대해 이분 탐색 실행
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            System.out.println(binarySearch(arr, target));
        }
    }

    // 이분 탐색 메서드: target이 존재하면 1, 없으면 0 반환
    static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (target == arr[mid])
                return 1; // 타겟 발견
            else if (target < arr[mid])
                right = mid - 1; // 타겟이 중간값보다 작다면 왼쪽으로 탐색 범위 축소
            else
                left = mid + 1; // 타겟이 중간값보다 크다면 오른쪽으로 탐색 범위 축소
        }
        return 0; // 타겟이 배열에 없음
    }
}