[JAVA]백준_10816_숫자카드2

문제링크

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

10816번: 숫자 카드 2

 

 

package BOJ;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_10816 {
    static int N,M;
    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i=0;i<M;i++){
            int findNum = Integer.parseInt(st.nextToken());


            bw.write((right_start(findNum)-left_start(findNum))+" ");
        }

        bw.flush();
        bw.close();
    }

    static int left_start(int findNum){
        int left = 0;
        int right = N;
        while(left <right) {
            int mid = (left + right) / 2;

            if (arr[mid] >= findNum) right = mid;
            else left = mid + 1;
        }

        return left;
    }

    static  int right_start(int findNum){
        int left = 0;
        int right = N;

        while(left<right){
            int mid = (left + right)/2;
            if(arr[mid] <= findNum) left = mid+1;
            else right = mid;
        }

        return left;
    }
}

카운트를 어떻게 해주어야할지 생각을 해보았다.

 

그래서

 

 

맨 처음 접근을 보통 이분탐색? 으로 해서

count를 세는 것을 앞뒤로 mid++해주면서 찾았다.

 

그렇게 하니까 시간 초과가 나서

 

혹시 몰라 syso에서 BufferedWriter로 바꾸어 보았다.

 

되는가 싶더니? 시간초과가 떴다.

 

 

인터넷에 검색해보니

이진탐색 알고리즘을 살짝 바꾼? upper bound, lower bound로 해결해야했다.

 

새로운 것을 또 알아갑니다,,,