BOJ) 수 찾기

수 찾기

1920번: 수 찾기

풀이

 

binary search인 것을 몰랐으면, 아마 시간 초과가 뜨고 나서야 시도했을 것 같다.

하지만, binary search라는 것을 알고 문제를 풀 때는 어렵지 않은 문제다.

binary search에서 가장 중요한 것은 여러번 언급했듯, 기준점이다.

이 문제에서는 기준점이 명확하게 특정 숫자다.

특정 숫자를 담고있는 배열의 index를 찾는 문제라고 생각하면되겠다.

 

기준이 되는 배열은 Arrays.sort를 통해 오름차순 정렬을 먼저 해줬다. (이진 탐색을 하기 위해)

그리고 수를 찾아야 하는 배열의 숫자를 차례대로 탐색했다.해당 숫자가 존재하면 true를 반환하고, 열람한 숫자가 목표보다 크면 right의 범위를 줄여주고, 작으면 left를 늘려줬다.이진 탐색을 모두 진행한 다음에도 찾을 수 없다면 false를 반환하며 메소드를 완성했다.

 

true / false에 따라 문제에서 원하는 답을 출력해주면서 답을 구할 수 있었다.문제를 풀면서 정말 많이 느끼지만, 문제에 대한 해석이 중요한 것 같다.이런 문제 유형은 2진 탐색으로 접근하는게 좋다는 것을 인지해두자.

 

코드

 

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

public class Main {
    final static String EXIST = "1", NO_EXIST = "0", NEWLINE="\n";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Object[] originObj = getDataObj(br);
        Object[] targetObj = getDataObj(br);
        br.close();
        solution((int)originObj[0],(int[])originObj[1], (int)targetObj[0], (int[])targetObj[1]);
    }

    private static Object[] getDataObj(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] numArr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)	numArr[i] = Integer.parseInt(st.nextToken());

        Object[] result = {n, numArr};
        return result;
    }

    private static void solution(int n, int[] originArr, int m, int[] targetArr) {
        StringBuffer sb = new StringBuffer();
        Arrays.sort(originArr);
        for(int target : targetArr) {
            if(inInNumber(target, n, originArr))    sb.append(EXIST);
            else                                    sb.append(NO_EXIST);
            sb.append(NEWLINE);
        }
        System.out.println(sb.toString());
    }

    private static boolean inInNumber(int target, int n, int[] originArr) { // binary search
        int left =0, right =n-1;

        while(left <=right) {
            int mid = (left+right)/2;
            int origin = originArr[mid];
            if(origin == target)        return true;
            else if(origin > target)    right = mid-1;
            else                        left = mid+1;
        }
        return false;
    }
}