[백준] BOJ - 10816 숫자 카드 2 java 자바 (실버4)

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

10816번: 숫자 카드 2

 

 

나의풀이

import java.io.*;
import java.util.*;
public class Main {
    static int[] card;
    public static int upperBound(int i){
        int start=0;
        int end=card.length;
        while(start<end){
            int mid=(start+end)/2;
            if(card[mid]>i){
                end=mid;
            }else{
                start=mid+1;

            }
        }
        return start;//start가 end와 같아질 때 반복문 탈출하므로 end랑 start는 같음
        
    }
    
    public static int lowerBound(int i){
        int start=0;
        int end=card.length;
        while(start<end){
            int mid=(start+end)/2;
            if(card[mid]>=i){
                end=mid;
            }else{
                start=mid+1;
            }
        }
        return start;//start가 end와 같아질 때 반복문 탈출하므로 end랑 start는 같음
    }
    
    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 n = Integer.parseInt(br.readLine());//상근이가 가진 카드 개수
        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());
        int[] list= new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++){
            list[i]=Integer.parseInt(st.nextToken());
        } 
        
        
        for(int i=0; i<m; i++){
            bw.write(Integer.toString(upperBound(list[i]) - lowerBound(list[i]))+" ");//중복된 수를 구하기 위해 상한, 하한 구하기 
        }
        bw.flush();
        br.close();
        bw.close();
        
    }
}

 

Tip.

일반적인 이진탐색과는 다르게 중복되는 값의 범위를 구해야함. upperbound lowerbound의 개념 필요 

 

참고사이트

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]