[BOJ][JAVA] 1920: 수 찾기

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

1920번: 수 찾기

 

---

오답노트(푸는 동안 사고과정 및 개선점)

이번 문제는 예전에 정렬로 대충 떼우려다가 못풀고 넘긴 문제다. 너무 예전에 틀려서 오답 코드를 올려도 그때의 사고과정이 생각나지 않는다. 이분탐색에 대한 개념을 습득하고 나서 풀게 된 문제이다. 기준점을 정하고, L, R을 움직이면서 범위를 (1/2)^n으로 좁혀가는 개념인데, 코드가 아직 어색해서 비슷한 유형의 문제를 좀 더 풀어봐야겠다.

---

정답코드

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main{

    public static int binarySearch(int[] arr, int target){
        int l=0; int r = arr.length-1;
        while (l<=r){
            int m = (l+r)/2;
            if(arr[m]<target) l = m+1;
            else if(arr[m]>target) r = m-1;
            else return 1;
        }
        return 0;
    }

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arrN = new int[n];
        for(int i=0; i<n;i++){
            arrN[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] arrM = new int[m];
        for(int i=0; i<m;i++){
            arrM[i] = sc.nextInt();
        }
        Arrays.sort(arrN);
        for(int X: arrM){
            System.out.println(binarySearch(arrN, X));
        }

        sc.close();
    }
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^