[ 백준 1920 / Java ] 수 찾기

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

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 복사

---

5
4 1 5 2 3
5
1 3 7 9 5

 

 

예제 출력 1 복사

---

1
1
0
0
1

 

 

풀이

---

이분 탐색(Binary Search)을 사용했다.

 

이분 탐색이란?
두부분으로 쪼개면서 탐색 한다.

 

이분 탐색 메커니즘
   1. 탐색 범위내의 배열의 중간인덱스를 구한다
   2. 중간 인덱스의 값과 key값을 비교
   3. 값이 중간 값보다 작다면 왼쪽 부분을, 값이 중간 보다 크다면 오른쪽 부분을 탐색한다. 같다면 해당 인텍스를 반환하고 종료.

 

NOTE
분할 정복과 이분 탐색의 차이점

분할 정복은 어떤 문제를 전첵적으로 해결하기 위해 부분적으로 나눠들어가면서 분할아혀 부분 문제를 해결하는 방식
이분 탐색은 유사하게 두 부분으로 나누어 들어가긴 하지만, 특정 값 또는 자료를 찾는 '탐색'이다.
   ex. up & down 게임 - 1~100 사이의 수 중 17을 정했을때 처음에 반을 나눈 50에서 up & down

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static int N; // N개의 정수
    static int M;
    static int[] nArr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        nArr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nArr[i] = Integer.parseInt(st.nextToken());
        }
        
        //배열은 정렬 시켜준다.
        Arrays.sort(nArr);
        
        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            // //찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력
            if (binarySearch((Integer.parseInt(st.nextToken()))) >= 0) {
                sb.append(1).append('\n');
            } else {
                sb.append(0).append('\n');
            }
        }
        System.out.println(sb);
    }
    public static int binarySearch (int key) {
        int left = 0; //탐색 범위의 왼쪽 끝
        int right = nArr.length - 1; // 탐색 범위의 오른쪽 끝
 
        // left가 right보다 커지기 전까지 반복
        while( left <= right) {
            int mid = (left + right) /2; // 중간 위치의 값
            // key 값이 중간 위치의 값보다 작을 경우
            if (key < nArr[mid])  {
                right = mid -1;
            }
            // key 값이 중간 위치의 값보다 클 경우
            else if (key > nArr[mid]) {
                left = mid + 1;
            }
             // key 값이 중간 위치의 값과 같을 경우
            else {
                return mid;
            }
        }
        // 찾고자 하는 값이 존재하지 않을 경우
        return -1;
    }
}