BOJ 10816 S4 숫자카드2

💻 문제

숫자 카드 2

문제 설명

주어진 배열에서 주어진 숫자의 개수를 센다.

• 예시 입력

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

• 예시 출력

3 0 0 1 2 0 0 2

🔐 풀이

아이디어

해시 맵으로 개수를 저장해놓고 key 값으로 조회해도 되지만,
이분 탐색을 연습하고 싶어서 이분 탐색으로 풀이했다.

중복 원소의 개수를 구하기 위해서 해당 숫자가 있는 가장 왼쪽 인덱스와 해당 숫자보다 큰 수 중 가장 작은 수의 인덱스를 찾아서 빼는 방법을 사용했다.

이를 각각 lower bound, upper bound로 부르는 듯하다.

각각 이분 탐색하지 않고 구하니 임계값에 대한 처리가 어려워 각각 이분 탐색을 통해 인덱스를 구해주었다 : lowerBound, upperBound 함수.

👉 제출 코드

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

public class Main {
    static int N; // 상근이가 가지고 있는 숫자 카드의 개수
    static int[] cards; // 숫자 카드에 적혀있는 정수
    static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cards = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        
        // 정렬
        Arrays.sort(cards);
        
        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int k = Integer.parseInt(st.nextToken());
            sb.append(upperBound(k) - lowerBound(k)).append(' ');
        }
        System.out.println(sb);
    }
    static int lowerBound(int k) {
        // "k 값 이상"을 가지고 있는 가장 작은 인덱스(처음 만난)
        int low = 0;
        int high = N;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (cards[mid] >= k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    static int upperBound(int k) {
        // "k 값 초과"를 가지고 있는 가장 작은 인덱스(처음 만난)
        int low = 0;
        int high = N;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (cards[mid] > k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

• 인텔리제이 최신 판을 깔아보니 코드를 자동완성 해주었다.
  이때, mid 값을 (low + high)/2가 아닌 다른 형태로 선언하였다.
  이는 해당 문제와는 관련이 없지만,
  high가 Integer.MAX_VALUE보다 클 때 overflow를 방지할 수 있다는 의미를 가진다.