[백준 1920]- 수찾기- JAVA [이분탐색, Arrays binarySearch 사용]

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 1920번

"수찾기" 포스팅입니다.

 

2가지 풀이법으로 풀어 보겠습니다.

 

1920번: 수 찾기

 

문제설명

문제는 되게 간단합니다.

두개의 배열을 받는데 밑에서 입력받는 숫자들이 위에 있는지 없는지 확인하고 있으면 1을 출력하고 없으면 0을 출력해줍니다.

 

먼저 이중 for문으로 풀었는데 바로 시간초과떴습니다.

 

=> 시간이 중요한 문제 그래서 "이분탐색" , Arrays.binarySearch 를 사용하면 됩니다.

 

먼저 이분탐색입니다.

간단하게 이분탐색을 설명하자면 먼저 배열이 정렬되어있어야합니다(중요)

그 후 어떤 값을 찾을 때 배열의 가운데 값이랑 비교해줍니다.

값이 배열중간값보다 작다 그러면 1~배열중간값 으로 검색범위를 줄여줍니다. -> 이렇게 절반씩 줄여주면서 값을 찾아주는 게 이분탐색입니다.

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

public class Main{
    public static int[] intA;

    public static int binarySer(int key){
        int lowIdx = 0;
        int highIdx = intA.length-1;

        while(lowIdx <= highIdx){
            int midIdx = (lowIdx + highIdx)/2;

            if(key < intA[midIdx]){
                highIdx = midIdx -1;
            }else if(key > intA[midIdx]){
                lowIdx = midIdx + 1;
            }else{
                return midIdx;
            }
        }
        return -1;
    }

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int nA = Integer.parseInt(br.readLine());
        intA = new int[nA];
        StringTokenizer stA = new StringTokenizer(br.readLine());

        for(int i=0; i<nA; i++){
            intA[i] = Integer.parseInt(stA.nextToken());
        }

        Arrays.sort(intA);

        int nB = Integer.parseInt(br.readLine());
        StringTokenizer stB = new StringTokenizer(br.readLine());
        for(int i=0; i<nB; i++){
            if(binarySer(Integer.parseInt(stB.nextToken())) >= 0){
                System.out.println("1");
            }else{
                System.out.println("0");
            }
        }
    }
}

 

이분 탐색을 구현한 부분입니다.

public static int binarySer(int key){
    int lowIdx = 0;
    int highIdx = intA.length-1;

    while(lowIdx <= highIdx){
        int midIdx = (lowIdx + highIdx)/2;

        if(key < intA[midIdx]){
            highIdx = midIdx -1;
        }else if(key > intA[midIdx]){
            lowIdx = midIdx + 1;
        }else{
            return midIdx;
        }
    }
    return -1;
}

 

아까 위에서 이분탐색에 대해 설명한듯이 low -> 첫번째 인덱스 high가 이제 배열의 끝값

찾을 때 까지 계속 잘라주면 됩니다.

 

 

두번쨰방법은 Arrays 에 binarySearch 메소드가 구현되어 있습니다.

이분탐색해주는 메소드입니다.

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

public class Main{

    public static int[] intA;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int nA = Integer.parseInt(br.readLine());
        intA = new int[nA];
        StringTokenizer stA = new StringTokenizer(br.readLine());

        for(int i=0; i<nA; i++){
            intA[i] = Integer.parseInt(stA.nextToken());
        }

        Arrays.sort(intA);

        int nB = Integer.parseInt(br.readLine());
        StringTokenizer stB = new StringTokenizer(br.readLine());
        for(int i=0; i<nB; i++){
            if(Arrays.binarySearch(intA ,Integer.parseInt(stB.nextToken())) >= 0){
                System.out.println("1");
            }else{
                System.out.println("0");
            }
        }
    }
}

이렇게 메소드를 사용하면 엄청 간단해지는 그래도 한 번쯤은 이분탐색을 구현하는 것도 좋은 거 같습니다.

 

궁금하신 점이 있으시면 댓글 남겨주세요

 

감사합니다~