[백준] CLASS2 1920번 : 수 찾기 - JAVA [자바]

 안녕하세요. 이번에는 자바 1920 수 찾기 문제를 풀어보려고 합니다.

 

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

1920번: 수 찾기

---

Problem

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

사진 1. 문제

---

Solution

import java.io.*;
import java.util.*;

public class Main {
    
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());    
        }
        
        int M = Integer.parseInt(br.readLine());
        Arrays.sort(arr);
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(binarySearch(num)) sb.append("1\n");
            else sb.append("0\n");
        }
       
        System.out.println(sb.toString());
    }
    
    public static boolean binarySearch(int num) {
        int start = 0;
        int end = arr.length - 1;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            if(arr[mid] == num) {
                return true;
            } else if(arr[mid] > num) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        
        return false;
    }
}

 

 이번 문제는 arr 배열을 만들어준 후 arr 배열에 N 개의 정수를 넣어준 후 Sort를 사용하여 오름차순 정렬을 해준다.

그다음 M 개의 수들을 arr 배열에 비교하면서 배열에 존재하는 숫자이면 1, 아니면 0을 출력해 주면 된다. 여기서 for문으로 전체적으로 다 훑어 보는 방법도 존재하지만, binarySearch를 이용하면 더 적은 시간을 사용해서 문제를 해결할 수 있다.

 

BinarySearch 핵심 코드

    public static boolean binarySearch(int num) {
        int start = 0;
        int end = arr.length - 1;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            if(arr[mid] == num) {
                return true;
            } else if(arr[mid] > num) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        
        return false;
    }

 

 BinarySearch는 시작점 0 과 배열의 크기를 끝점으로 지정하고 그 중간인 mid((start + end) / 2)를 구해서 배열의 중간값과 찾고자 하는 타깃값을 비교하고 타깃값이 크면 시작점을 mid + 1 해주고 다시 mid를 구하거나, 만약 타깃값이 작으면 끝점을 mid - 1로 변경 후 다시 mid 값을 구하면서  시작점이 끝점보다 커질 경우 while문을 종료시키는 방식으로 구현하면 된다.  for문으로도 구현이 가능하지만 for 문은 O(n)의 시간 복잡도를 가지고 있고 BinarySearch는 O(log n)의 시간 복잡도를 가지고 있어서 배열의 크기가 커질수록 BinarySearch를 사용하는 것이 더 적합하다는 것을 알 수 있다.

 

---

Performance

사진 2. 실행 결과