[1920] 수 찾기 (JAVA)

# 문제 설명

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을 출력한다.

 

# 정답 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            arr[n] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int m = 0; m < M; m++) {
            int target = Integer.parseInt(st.nextToken());
            boolean find = false;
            int start = 0;
            int end = N-1;

            while (start <= end) {
                int midIdx = (start+end)/2;
                int midVal = arr[midIdx];

                if (target < midVal) {
                    end = midIdx-1;
                }
                else if (midVal < target) {
                    start = midIdx+1;
                }
                else {
                    find = true;
                    break;
                }
            }

            if (find) {
                sb.append("1\n");
            }
            else {
                sb.append("0\n");
            }
        }

        System.out.print(sb);
    }
}

 

크기가 N인 배열을 만들고 입력 받은 값을 저장한다.

이진 탐색을 이용하여 타깃 데이터가 있는지 확인하기 위해 오름차순 정렬해준다.

 

M번 만큼 반복하며 해당 데이터가 배열에 있는지 검사한다.

데이터가 있는지 확인하기 위해 find를 사용한다. 있으면 true, 없으면 false이다.

시작 위치 start는 0으로 설정하고, 끝 위치 end는 N-1로 설정한다.

 

start가 end보다 작거나 같을 때까지 반복한다.

중간값 인덱스 midIdx는 (start + end) / 2로 설정하고, 배열에서 midIdx 위치의 값을 midVal에 저장한다.

• 타깃 데이터보다 중간값이 크면, end를 midIdx-1로 설정한다.
• 타깃 데이터보다 중간값이 작으면, start를 midIdx+1로 설정한다.
• 타깃 데이터와 중간값이 같으면, find를 true로 바꾸고 while문을 종료한다.

find가 true이면 1을, false이면 0을 출력한다.