[BOJ 10816] 숫자 카드 2 - JAVA, Silver 4

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

10816번: 숫자 카드 2

풀이

사용한 알고리즘 : 이진탐색, 해쉬 맵 자료구조

 

풀이전략

이진탐색을 사용하지 않고, 해쉬 맵 또는 배열 카운팅 방식으로 풀이할 수도 있는 문제이다.

(실제 이진 탐색은 시간 복잡도가 O(nlogn)인데 반해, 위 방법들의 시간 복잡도는 O(n)으로 더 빠르다.)

 

하지만 이진 탐색 기법을 사용하여 문제를 풀이해보겠다.

 

C++과 python과 달리 JAVA에는 lower_bound와 upper_bound를 구해주는 함수가 없다.

따라서 이 함수들을 실제로 구현해줘야하는데,

각 함수들이 어떤 방식으로 인덱스 값을 도출하는지 알아보자.

 

위와 같은 배열이 있을 때 key 값으로 4가 주어졌다면

lower_bound는 3, upper_bound는 6이다.

lower_bound는 key 값을 가지는 값들 중 가장 작은 인덱스를 나타내고,

upper_bound는 key 값을 가지는 값들 중 가장 큰 인덱스의 다음 인덱스를 나타내기 때문이다.

 

보통의 이진탐색을 통해서는 특정 값을 갖는 인덱스를 찾을 수는 있지만,

우리가 구해야하는 key 값에 대응되는 인덱스들의 총 개수를 구할 때는

lower_bound와 upper_bound를 구한 뒤, upper_bound - lower_bound하여 답을 구해야한다.

 

먼저 아래는 lower_bound를 구하는 메소드 코드로

static int lowerBound(int key){
    int start=0;
    int end = N;  // N-1이 아닌 N으로 배열의 총 개수보다 +1인 수를 end 값의 초기값으로 사용한다.

    while(start<end){
        int mid=(start+end)/2;

        if(key<=cards[mid]){
            end=mid;
        }
        else{
            start=mid+1;
        }
    }
    return start;
}

시작점과 끝점이 동일해지기 전까지 반복하면서

만약 key 값이 중간값보다 작거나 같으면 끝점을 중간지점으로,

만약 key 값이 중간값보다 크면 시작점을 중간지점+1로 변환한다.

 

 

다음 upper_bound는

static int upperBound(int key){
    int start=0;
    int end = N;

    while(start<end){
        int mid=(start+end)/2;

        if(key<cards[mid]){
            end=mid;
        }
        else{
            start=mid+1;
        }
    }
    return start;
}

 

key 값이 중간지점 값보다 작으면 끝점을 중간지점 값으로,

key 값이 중간지점 값보다 크거나 같으면 시작점을 중간점+1로 변환한다.

 

그리고 upper_bound - lower_bound 식을 통해

배열 내에서 key 값의 개수를 구할 수 있다.

 

제출코드

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

public class Main {

    static int N;
    static int cards[];

    static int lowerBound(int key){
        int start=0;
        int end = N;

        while(start<end){
            int mid=(start+end)/2;

            if(key<=cards[mid]){
                end=mid;
            }
            else{
                start=mid+1;
            }
        }
        return start;
    }

    static int upperBound(int key){
        int start=0;
        int end = N;

        while(start<end){
            int mid=(start+end)/2;

            if(key<cards[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));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        cards = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            cards[i]=Integer.parseInt(st.nextToken());
        };
        Arrays.sort(cards);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;++i){
            int val = Integer.parseInt(st.nextToken());
            bw.write(upperBound(val)-lowerBound(val)+" ");
        }
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}

 

아래 블로그에 해당 문제에 대해 더 자세히 설명되어 있는데,

필요하면 참고하길 바란다.

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