📖 [백준알고리즘 풀이] Q.1920 수 찾기 문제 풀이 - java

📖 문제

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

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

🔍 접근법

Q.1920 수 찾기 문제입니다.

n개의 정수가 주어지고 그 중에 x라는 정수가 존재하는지를 알아내는 문제입니다.

단순히 x라는 정수가 존재하는지를 알아내면 되기 때문에

set을 이용하여 풀었습니다.

set에 n개의 정수들을 넣어주고 set에 x가 있는지를 확인하면 끝입니다.

문제를 풀고나니 분류가 binary search 로 되어있어

binary search 를 이용해서도 풀어보았습니다.

n개의 정수들을 입력받고 정렬을 해준 후

binary search 를 이용하여

start 지점과 end 지점의 중간 mid에

x가 있다면 1을 출력하도록 하고

mid 값이 x보다 작다면 현재 mid 보다 앞에 있는 값들은 전부 x보다 작은 것이므로

mid 의 전에 있는 수들을 확인할 필요가 없습니다.

start 를 mid+1 로 조정해줍니다.

반대로 mid 값이 x보다 크다면 mid의 뒤에 값들은 전부 x보다 큰 수이므로 확인할 필요가 없으니

end 를 mid-1로 조정해줍니다.

이를 반복하여

n개의 정수들 중 x가 있는지를 확인할 수 있습니다.

💻 코드

set을 이용한 첫 번째 풀이 방법

package problem.binary_search.Q1920;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main_1920_1 {
    static int n, m;
    static Set<Integer> set = new HashSet<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String[] temp = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            set.add(Integer.parseInt(temp[i]));
        }
        m = Integer.parseInt(br.readLine());
        temp = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(temp[i]);
            if (set.contains(num)) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }
        br.close();
        System.out.println(sb.toString());
    }
}

binary search를 이용한 두 번째 풀이 방법

package problem.binary_search.Q1920;

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

public class Main_1920_2 {
    static int n, m;
    static int[] numbers;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        String[] temp = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(temp[i]);
        }

        m = Integer.parseInt(br.readLine());
        temp = br.readLine().split(" ");

        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(temp[i]);
            binarySearch(0,n-1,num);
        }

        br.close();
        System.out.println(sb.toString());
    }

    private static void binarySearch(int start,int end,int data){
        Arrays.sort(numbers);
        while (start <= end) {
            int mid = (start + end) / 2;
            if (numbers[mid] == data) {
                sb.append("1\n");
                return;
            }
            else if(numbers[mid] < data){
                start = mid+1;
            }
            else{
                end = mid-1;
            }
        }
        sb.append("0\n");
    }
}

Written on March 19, 2021