[백준] 10816 숫자 카드 2 - 이분탐색(binary search) JAVA

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

10816번: 숫자 카드 2

코드설명

이 문제는 HashMap, 배열, 이분탐색 을 활용하여 풀 수 있는 문제입니다.

HashMap과 배열을 사용하면 쉽게 풀수 있지만, 이분탐색으로 풀어보고싶어서 이분탐색으로 접근했습니다.

 

이 문제의 핵심은

lowerBound를 통해 해당 target을 포함하는 숫자의 Index를 가져옵니다.

upperBound를 통해 해당 target을 포함하는 숫자의 Index + 1 을 가져옵니다.

 

이 과정에서 일반적인 이분탐색과 다릅니다.

일반적인 이분탐색을 사용할경우

for(int i=0;i<M;i++) {
    int answer = 0;
    int startIdx = 0, endIdx = N - 1;
    int target = Integer.parseInt(st.nextToken());
 
    while(startIdx <= endIdx) {
        int mid = ( startIdx + endIdx) / 2;
        if(A[mid] == target) {
            answer = 1;
            break;
        }
        if(A[mid] < target) startIdx = mid + 1;
        else if (A[mid] > target) endIdx = mid - 1;
    }
    System.out.println(answer);
}

 

• 위의 코드와 같이 endIdx = N -1, 종료조건은 startIdx <= endIdx 입니다.

하지만, upperBound와 lowerBound를 구현할시에는 startIdx와 endIdx가 같아진다면 바로 종료시키는 처리를 통해 진행했습니다. 

또한 LowerBound 같은경우 target 과 A[midIdx]가 <=  처리를 통해 10, 10, 10 이 있을때 endIdx가 startIdx로 이동하게 처리합니다.

upperBOund같은경우 target과 A[midIdx] 를 < 처리를 통해\ 둘의 값이 같아질때, 즉 10 , 10 , 10 이 있을때 startIdx가 endIdx쪽으로 다가오도록 처리했습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N;
	public static int[] A;
	public static int M;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	A = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		A[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(A);
    	
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	for(int j=0;j<M;j++) {
    		int target = Integer.parseInt(st.nextToken());
    		int lowerBoundValue = lowerBound(target);
    		int upperBoundValue = upperBound(target);
//    		System.out.print(upperBoundValue - lowerBoundValue+" ");
    		sb.append(upperBoundValue - lowerBoundValue).append(" ");
    	}
    	System.out.println(sb.toString());
    }
    
    //target의 가장 작은 작은 Index
    public static int lowerBound(int target) {
    	int startIdx = 0;
    	int endIdx = N;
    	
    	while(startIdx < endIdx) {
    		int midIdx = (startIdx + endIdx) / 2;
    		if(target <= A[midIdx]) {
    			endIdx = midIdx;
    		}else {
    			startIdx = midIdx + 1;
    		}
    	}
    	
    	return endIdx;
    }
    
    //target의 가장 큰 Index 보다  한 칸 더 높음
    public static int upperBound(int target) {
    	int startIdx = 0;
    	int endIdx = N;
    	while(startIdx < endIdx) {
    		int midIdx = (startIdx + endIdx ) / 2;
    		if(target < A[midIdx]) {
    			endIdx = midIdx;
    		}else {
    			startIdx = midIdx + 1;
    		}
    	}
    	return endIdx;
    }
    
    
}

 

 

참고

https://we1cometomeanings.tistory.com/232