[JAVA] 백준 10816 숫자 카드 2

10816번: 숫자 카드 2 (acmicpc.net)

10816번: 숫자 카드 2

 

 

풀이 과정 

 

- 중복 원소의 개수를 구해야 함

- 중복 원소의 왼쪽 끝 값과 오른쪽 끝 값을 각각 알아내는 

- lower_bound /Upper_bound를 이용 

- 중복 원소에 대한 길이 = (상한 - 하한)

 

[C언어 / 백준 - 10816] 숫자 카드2 / lower_bound, Upper_bound (tistory.com)

[C언어 / 백준 - 10816] 숫자 카드2 / lower_bound, Upper_bound

 

이분 탐색

- 정렬된 수를 분할하여 찾고자 하는 k값의 index를 찾는 알고리즘 

 

lower_bound

 - 정렬된 수들 중 찾고자 하는 k 이상의 최초값 index를 찾는 알고리즘 

 - 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치 

 

Upper_bound 

- 정렬된 수들 중 찾고자 하는 k를 초과한 최초값의 index를 찾는 알고리즘 

- 찾고자 하는 값을 초과한 값을 처음 만나는 위치 

 

 

정답

 

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

public class Main {
	
	//Lower Bound = 일치하는 숫자가 처음 나타나는 지점
	public static int Lower_bound(int target[] , int key)
	{
		int start = 0;
		int end = target.length;
		
		while(start<end)
		{
			int mid = (start+end)/2;
			
			if(key<=target[mid])
			{
				end = mid;
			}
			else
			{
				start = mid+1;
			}
		}
		return start;
	}
	
	//Upper Bound = 일치하는 숫자 다음 수가 나타나는 지점
	public static int Upper_bound(int target[], int key)
	{
		int start = 0;
		int end = target.length;
		
		while(start<end)
		{
			int mid = (start+end)/2;
			
			if(key<target[mid])
			{
				end = mid;
			}
			else
			{
				start = mid+1;
			}
		}
		
		return start;
		
	}
	

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        int card[] = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
        {
        	card[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(card);
        
        int m = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++)
        {
        	int key = Integer.parseInt(st.nextToken());
        	
        	bw.write(Upper_bound(card,key)- Lower_bound(card,key)+" ");
        }
        
        bw.flush();
        bw.close();
    }
}