이것저것 개발 블로그

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

풀이)

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

public class Main_BJ_1920_수찾기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        // 이분 탐색 위한 정렬
        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        int[] find = new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++)
            find[i] = Integer.parseInt(st.nextToken());

        for(int i=0; i<m; i++) {
            //binary Search
            int low = 0;
            int high = n-1;
            int mid = 0;
            int key = find[i];
            boolean flag = false; // 탐색 성공
            while (low <= high) {
                mid = (low + high) / 2;

                if(key == arr[mid]) {
                    System.out.println(1);
                    flag = true;
                    break;
                }
                else if(key < arr[mid]){
                    high = mid-1;
                }
                else{
                    low = mid+1;
                }
            }//while
            if(!flag){
                System.out.println(0);
            }

        }//for

    }
}

이진 탐색(이분 탐색)을 연습해보려고 쉬운 문제를 골라봤다.

일단, 범위가 어마무시하기 때문에 이진 탐색이라고 생각하고 있어야 한다!!

따라서, 입력받은 것들을 배열로 오름차순으로 만들어주고, 이진탐색을 수행하면서 key가 존재하는지 살펴보면 된다.

<이진탐색 간단 정리>

1. 탐색할 배열 정렬

2. low, high, mid 값 설정

• 초기엔 low가 0, high가 맨 마지막 인덱스
• mid는 계속 갱신해나가는데 (low+high) / 2이다

3. 3가지 경우로 나눌 수 있음

• key == 배열[mid]
  • 바로 탈출하면 된다
• key < 배열[mid]
  • 찾는 값은 가운데보다 왼쪽에 존재한다는 의미
  • high = mid-1로 갱신
• key > 배열[mid]
  • 찾는 값은 가운데보다 오른쪽에 존재한다는 의미
  • low = mid+1로 갱신

4. 3의 과정을 low <= high가 될 때까지 반복하면 된다. 이 조건까지 온다면 값이 존재하지 않는다는 의미!