[백준 - 1920] 수 찾기 .java

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

 

 

 

Solution

<문제 분석>

n의 최대 범위가 100,000이기 때문에 이진 탐색의 복잡도로 풀었다. 하지만 입력받은 배열은 정렬이 되지 않았기에 정렬함수를 통해 정렬부터 한다.

 

이진탐색의 포인트

• mid 값 정하는 것
• 구한 mid값과 찾는 값(target)을 비교하여 새로운 start와 end를 구한다
• 새롭게 구한 start,end의 범위를 통해 새로운 mid값을 구한다

-> 이 문제에서

• mid = (start + end) / 2
• mid < target : start = mid +1
• mid > target : end = mid  - 1
• mid == taget : 찾았기 때문에 종료
• 하지만 찾았으면 1, 못찾으면 0을 출력해야한다 -> 찾음을 나타내는 boolean 변수를 이용

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        //오름차순으로 정렬
        Arrays.sort(nums);

        //찾아야하는 수의 개수
        int m  = sc.nextInt();
        for(int i = 0 ; i < m; i++) {
            //찾음을 나타내는 변수
            boolean find = false;
            //찾고자 하는 수
            int target = sc.nextInt();
            //이진 탐색
            int start = 0; //0번째 인덱스부터 시작
            int end = nums.length - 1;

            //start가 end를 넘어가면 종료
            while (start <= end) {
                int mid = (start + end) / 2;//중앙 인덱스 계산
                int vmid = nums[mid];//중앙값
                //중앙값이 찾는 값이면
                if(vmid == target) {
                    find = true;
                    break;
                } else if(vmid < target) {//중앙값이 작으면
                    start = mid + 1;//오른쪽셋
                } else {//중앙값이 더 크면
                   end = mid - 1;
                }
            }
            //출력
            if(find) {
                System.out.println(1);
            } else{
                System.out.println(0);
            }

        }

    }

}