백준-10816번/숫자 카드 2 (java)

 

 

 

숫자 카드 문제와 유사하지만 숫자 카드 2 문제는 숫자카드가 중복되어 있어서 카드 갯수를 다 구해야 한다는 차이점이 있다. 

이 문제도 숫자 카드 문제와 똑같이 이진 탐색으로 Mid값을 구해주고 앞 뒤로 중복된 카드가 있는지 구해주면 되는 줄 알고 코드를 작성했다.

 

<시간초과>

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

public class Main {
    static int N;
    static int 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));

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

        StringTokenizer 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 num = Integer.parseInt(st.nextToken());
            bw.write(BinarySearch(num)+" ");
        }
        bw.flush();

    }
    public static int BinarySearch(int num) {
        int Tail = 0;
        int Head = N - 1;
        int count=0;
        while (Head >= Tail) {
            int Mid = (Head + Tail) / 2;
            int MidValue = arr[Mid];
            if (MidValue > num) {
                Head = Mid - 1;
            } else if (MidValue < num) {
                Tail = Mid + 1;
            } else {
                int temp=Mid;
                count++;
                while (Mid<N-1) {
                    if(arr[Mid+1]==num){
                        count++;
                        Mid++;
                    }
                    else{
                        break;
                    }
                }
                Mid=temp;
                while(Mid>0){
                    if(arr[Mid-1]==num){
                        count++;
                        Mid--;
                    }
                    else{
                        break;
                    }
                }
                break;
            }
        }

        return count;
    }
}

 

이 코드의 치명적인 문제는 찾고자 하는 숫자를 찾았는데 그 앞으로 500,000개의 숫자가 다 똑같은 숫자라면 무조건 시간초과가 뜰 수 밖에 없다.

 

이 방법 외에는 달리 방법이 떠오르지 않아서 구글링을 한 결과 조금 다른 이진탐색을 수행해야 한다는 것을 알게 되었다.

 

public static int findStart(int num){
    int Head = arr.length;
    int Tail=0;
    while(Head>Tail){
        int Mid = (Head+Tail)/2;
        if(num<=arr[Mid]){
            Head=Mid;
        }
        else{
            Tail=Mid+1;
        }
    }
    return Tail;
}

public static int findLast(int num){
    int Head = arr.length;
    int Tail = 0;
    while(Head>Tail){
        int Mid = (Head+Tail)/2;
        if(num<arr[Mid]){
            Head=Mid;
        }
        else{
            Tail=Mid+1;
        }
    }
    return Tail;
}

 

findStart ==> 찾고자 하는 숫자가 시작되는 곳의 인덱스를 찾는다.

findLast ==> 찾고자 하는 숫자가 끝나는 곳의 다음 인덱스를 구한다. 

 

findLast-findStart == 찾고자 하는 값의 갯수

 

 

<전체 코드>

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

public class Problem10816 {
    static int N;
    static int 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));

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

        StringTokenizer 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 num = Integer.parseInt(st.nextToken());
            bw.write(findLast(num)-findStart(num)+" ");
        }
        bw.flush();

    }
    public static int findStart(int num){
        int Head = arr.length;
        int Tail=0;
        while(Head>Tail){
            int Mid = (Head+Tail)/2;
            if(num<=arr[Mid]){
                Head=Mid;
            }
            else{
                Tail=Mid+1;
            }
        }
        return Tail;
    }

    public static int findLast(int num){
        int Head = arr.length;
        int Tail = 0;
        while(Head>Tail){
            int Mid = (Head+Tail)/2;
            if(num<arr[Mid]){
                Head=Mid;
            }
            else{
                Tail=Mid+1;
            }
        }
        return Tail;
    }

}