백준 10816. 숫자 카드2 (JAVA)

○ 문제 요약

상근이는 숫자 카드를 N개 가지고 있다. 다음으로 상근이가 가지고 있는 숫자 카드가 몇 개인지 구해야 할 M개의 정수가 주어진다. 주어진 정수를 상근이가 몇 개 가지고 있는지 출력하자. 

 

○ 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

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

        for(int i = 0 ; i < N ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < M; i++) {
            int value = Integer.parseInt(st.nextToken());
            sb.append(upperBound(value) - lowerBound(value)).append(" ");
        }
        System.out.println(sb);
    }

    public static int lowerBound(int value){

        int lo = 0;
        int hi = arr.length;

        while(lo < hi){ // 둘이 같아질 때까지
            int mid = (lo + hi)/2;

            if(value <= arr[mid]){
                hi = mid;
            }else{
                lo = mid +1;
            }
        }
        return lo;
    }

    public static int upperBound(int value){
        int lo = 0;
        int hi = arr.length;

        while(lo < hi){ // 둘이 같아질 때까지
            int mid = (lo + hi)/2;

            if(value < arr[mid]){
                hi = mid;
            }else{
                lo = mid +1;
            }
        }
        return lo;
    }

}

이전 포스팅과 마찬가지로 이분 탐색법을 사용했다. 차이점은 이번 문제는 중복된 숫자가 있다는 것이다. 

백준 1920. 수 찾기(JAVA)

 

먼저 이분 탐색을 할 때 중요한 것은 정렬을 해야 한다는 것이다. 상근이가 가지고 있는 숫자 카드를 오름차순으로 정렬해주자. 

Arrays.sort(arr);

그리고 이 문제의 핵심이라고 할 수 있는 중복된 숫자 카드를 찾는 것이다. 여기서 많은 고민을 했고 다른 분의 풀이를 보고 해결할 수 있었다. 

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

 

해당 value값의 가장 작은 인덱스 값과 value값의 가장 큰 인덱스의 다음 인덱스를 반환받아서 빼면 중복된 숫자가 몇 개인지 알 수 있다.

 

먼저 lowerBound()를 구하는 과정을 보도록 하자.

그림에 있는 과정에서 마지막 과정이 지나고 나면 lo = 7이고 hi = 7로 둘의 값이 같아지게 된다. 그러므로 10의 가장의 작은 인덱스는 7이 반환된다. upperBound()를 구하는 과정을 보도록 하자. 

 

lo = 10이고 hi = 10으로 둘의 값이 같아져 lo의 값이 반환된다. 

 

sb.append(upperBound(value) - lowerBound(value).append(" ");

 

sb.append(10 - 7).append(" ");

 

sb.append(3).append(" ");

 

상근이가 10이 쓰여있는 숫자 카드를 3개 가지고 있는 것을 알 수 있다. 지금까지의 과정을 M만큼 반복 수행하면 주어진 M개의 숫자를 상근이가 몇 개 가지고 있는지 알 수 있다. 

 

○ 결과