백준 문제 풀이: [10816] 숫자 카드 2 (JAVA)

---

문제 링크: https://www.acmicpc.net/problem/10816

문제 설명:

숫자 카드를 여러 개 가지고 있을 때, 특정한 숫자가 몇 개 포함되어 있는지 찾아야 합니다. 이를 위해 이진 탐색을 활용하여 빠르게 개수를 찾는 방법을 사용해야 합니다.

입력으로 두 개의 정수 리스트가 주어집니다.

• N: 첫 번째 리스트의 크기
• N개의 정수: 숫자 카드 리스트
• M: 두 번째 리스트의 크기
• M개의 정수: 확인할 숫자 리스트

각 확인할 숫자에 대해, 숫자 카드 리스트에서 몇 개 포함되어 있는지 출력해야 합니다.

---

문제 해결 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 및 배열 저장
        int N = Integer.parseInt(br.readLine());
        int[] list = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list); // 정렬 필수 (이진 탐색을 위해)

        // M 입력 및 탐색
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            // 특정 값의 개수 = upperBound - lowerBound
            sb.append(upperBound(list, key) - lowerBound(list, key)).append(' ');
        }

        System.out.println(sb);
    }

    // lowerBound: 특정 값 이상이 처음 등장하는 위치 찾기
    private static int lowerBound(int[] list, int key) {
        int lo = 0, hi = list.length;

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (list[mid] >= key) {
                hi = mid; // key 이상이 처음 나타나는 위치를 찾기 위해 상한 조정
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    // upperBound: 특정 값보다 큰 값이 처음 등장하는 위치 찾기
    private static int upperBound(int[] list, int key) {
        int lo = 0, hi = list.length;

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (list[mid] > key) {
                hi = mid; // key 초과하는 값의 첫 위치를 찾기 위해 상한 조정
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

---

코드 설명

이 문제에서는 특정 숫자가 몇 개 존재하는지를 빠르게 찾기 위해 이진 탐색(Binary Search)을 활용했습니다.

• 핵심 알고리즘: lowerBound와 upperBound를 이용하여 특정 숫자의 개수를 찾습니다.
• 구현 세부사항:
  • 먼저 주어진 숫자 리스트를 정렬해야 합니다.
  • lowerBound: 찾는 값 이상이 처음 등장하는 위치를 반환합니다.
  • upperBound: 찾는 값보다 큰 값이 처음 등장하는 위치를 반환합니다.
  • 해당 숫자의 개수는 upperBound - lowerBound 로 계산됩니다.
• 시간 복잡도 분석:
  • 정렬: O(N log N)
  • 이진 탐색: O(log N)
  • M개의 숫자에 대해 탐색 수행: O(M log N)
  • 총 시간 복잡도: O(N log N + M log N) → 매우 효율적

---

결과

예제 테스트 케이스:

입력:
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

코드는 효율적으로 동작하며, O(N log N + M log N)의 시간 복잡도로 해결할 수 있습니다.

더 나은 방법이나 다른 접근 방식이 있다면 댓글로 공유해주세요!