[백준10816] 숫자 카드 2[java]

---

이 문제는 단순한 이분탐색으로는 풀 수 없는 문제였다. 여러가지로 시도해봤지만 결국 시간초과 오류.... 거기다가 

println을 사용해도 시간초과가 떴다.

 

결국 모든 데이터를 배열에 넣고 찾고 싶은 값 num의 범위를 찾아냈다.

 

lower와 upper메소드를 만들어 마지막에 upper의 값과 lower의 값을 빼는 것이다.

 

그리고 출력은 BufferedWriter를 이용하여 마무리 했다.

 

코드

package baekjoon;

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

public class num_card2 {
    static int[] arr1;
    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());
        
        arr1 = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<arr1.length;i++){
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr1);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i<m;i++){
            int num = Integer.parseInt(st.nextToken());
            bw.append((upper_bound(num))-(lower_bound(num))+" ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int lower_bound(int num) {//num이 처음 나오는 index
        int start = 0, last = arr1.length-1,mid;
        while(start<last){
            mid = (start+last)/2;
            if(arr1[mid] >=num){
                last = mid;
            }else{
                start = mid+1;
            }
        }
        return last;
    }

    public static int upper_bound(int num) {//num의 값보다 큰 값이 처음 나오는 index
        int start = 0, last = arr1.length-1,mid;
        while(start<last){
            mid = (start+last)/2;
            if(arr1[mid] > num){
                last = mid;
            }else{
                start = mid+1;
            }
        }
        if(arr1[last] == num) last++;
        return last;
    }
}