[알고리즘/백준] 1920번 : 수 찾기(Java)

문제	1920번 : 수 찾기
문제링크	https://www.acmicpc.net/problem/1920
난이도	S4
언어	Java
분류	이분 탐색 | 자료구조, 정렬, 이분 탐색, 해시를 활용한 집합과 맵

 

 

📌 최종 정답 코드

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));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            // N 입력
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];

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

            // 정렬
            Arrays.sort(arr);

            // M 입력
            int m = Integer.parseInt(br.readLine());

            // M개의 수 입력 후 이진 탐색
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                int target = Integer.parseInt(st.nextToken());
                if (binarySearch(arr, target)) {
                    bw.write("1\n");
                } else {
                    bw.write("0\n");
                }
            }

            // flush & close
            bw.flush();
            bw.close();
            br.close();
        }

        private static boolean binarySearch(int[] arr, int target) {
            int left = 0;
            int right = arr.length - 1;

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

                if (arr[mid] == target) {
                    return true;
                } else if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            return false;
        }
}

📌 구해야 하는 정답

- M개의 줄에 답을 출력. 존재하면 1을, 존재하지 않으면 0을 출력

 

 

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. A 배열을 정렬합니다.
3. 배열 안에 값이 존재하는지 확인하는 이분 탐색을 구현합니다.
4. M개의 수들에 대해 이분 탐색을 진행해 A 배열 안에 존재하는지 확인합니다.