이분탐색 (백준 10816 숫자 카드2)

 숫자 카드2 라는 문제를 풀어보았다. 정렬을 활용해서 풀었지만 이분 탐색 , 배열에 저장 등 다양한 풀이 방법이 있다는 걸 알게되었고 그 중 이분탐색으로 정리하고자 한다.

 

이분탐색 개념

먼저 이분탐색 개념에 대해 알아보자. 이름 그대로 두개로 나누어서 탐색한다는 뜻이다. 처음에 low값과 high값을 각각 정렬된 배열의 시작점과 끝점으로 정하고 그 중간지점을 mid값으로 정한다.

 

 만약 데이터의 중복이 없고 데이터와 같은 값을 찾았으면 바로 index를 리턴해주면 된다 

하지만 데이터에 중복이 있으면 upperbound와 lowerbound를 찾아 시작index와 끝index를 찾아 주어야한다.

 

 

문제

 이 문제는 데이터에 중복이 있기 때문에 upperbound와 lowerbound를 통해 data중에 index가 가장 큰 것과 작은 것을 각각 구하여 갯수를 구하면 될 것이다.

 

풀이

1. 찾고자 하는 데이터를 정렬한다.

2. key 값에 따라 upperbound와 lowerbound를 찾아 둘을 빼면 갯수를 찾을 수 있다.

import java.util.*;
import java.io.*;

public class Main{

    static int cardN[];
    static int cardM[];

    private static int lowerBound(int num) {
        int min = 0;
        int max = cardN.length;
        // min과 max가 같아질 때 까지 반복
        while(min < max) {
            int half = min+(max-min)/2;
            if(num <= cardN[half]) {
                max = half;
            }
            else {
                min = half + 1;
            }
        }
        return min;
    }

    private static int upperBound(int num) {
        int min = 0;
        int max = cardN.length;
        // min과 max가 같아질 때 까지 반복
        while(min < max) {
            int half = min+(max-min)/2;
            if(num < cardN[half]) {
                max = half;
            }
            else {
                min = half + 1;
            }
        }
        return min;
    }

    static int search(int x){
        return upperBound(x)-lowerBound(x);
    }

    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st=new StringTokenizer(br.readLine());
        cardN = new int[N];
        for(int i = 0;i<N;i++){
            cardN[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cardN); //cardN을 오름차순으로 정렬 -> 이분탐색을 위해 필수.
        int M = Integer.parseInt(br.readLine());
        cardM = new int[M];
        st=new StringTokenizer(br.readLine());
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<M;i++){
            sb.append(search(Integer.parseInt(st.nextToken()))).append(" ");
        }
        System.out.print(sb);
    }
}

 

피드백

이분 탐색 문제는 많이 풀어보지 않아 아직 익숙하지 않고 개념도 확실하지 않은 것 같다. 다른 여러 문제를 풀며 좀 더 개념을 확립하고 익숙해질 필요가 있어 보인다.