[P&B] #81 BAEKJOON 10816

백준 10816번 숫자 카드 2 JAVA

문제 설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

나의 문제 풀이 코드

import java.util.*;
import java.io.*;
public class bj10816 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int M = Integer.parseInt(br.readLine());
        long[] arrM = new long[M];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            arrM[i] = Long.parseLong(st2.nextToken());
        }

        for (int i = 0; i < M; i++) {
            int result = countOccurrences(arrN, arrM[i]);
            bw.write(result+" ");
        }

        bw.flush();

    }

    public static int countOccurrences(long[] arr, long target) {
        int firstOccurrence = findFirstOccurrence(arr, target);
        if (firstOccurrence == -1) {
            // 원하는 요소가 배열에 없는 경우
            return 0;
        }

        int lastOccurrence = findLastOccurrence(arr, target);
        return lastOccurrence - firstOccurrence + 1;
    }

    public static int findFirstOccurrence(long[] arr, long target) {
        int left = 0;
        int right = arr.length - 1;
        int firstOccurrence = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                firstOccurrence = mid;
                right = mid - 1; // 왼쪽 부분 탐색
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return firstOccurrence;
    }

    public static int findLastOccurrence(long[] arr, long target) {
        int left = 0;
        int right = arr.length - 1;
        int lastOccurrence = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                lastOccurrence = mid;
                left = mid + 1; // 오른쪽 부분 탐색
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return lastOccurrence;
    }
}

 

문제 풀이 코멘트

처음엔 for문으로만 풀려고 했다가 시간초과의 아픔을 맛보았습니다.. (그래 실버 문제가 호락호락할리가)

그래서 이진탐색법을 사용해서 다시 풀었습니다.

이진 탐색법 (Binary Search)

이진 탐색법은 정렬된 배열에서 특정 요소를 효율적으로 찾기 위한 알고리즘입니다. 이 알고리즘은 배열의 중간 요소와 찾고자 하는 값을 비교하고, 중간 요소가 찾고자 하는 값보다 크면 배열의 왼쪽 절반에서 탐색을 계속하고, 중간 요소가 작으면 배열의 오른쪽 절반에서 탐색을 계속합니다. 이러한 과정을 반복해서 원하는 요소를 찾을 때까지 반복합니다.

이진 탐색의 주요 특징은 다음과 같습니다:

• 배열이 정렬되어 있어야 합니다.
• 각 단계에서 탐색 범위가 절반으로 줄어듭니다.
• 시간 복잡도는 O(log n)으로 매우 효율적입니다.

이진 탐색은 검색 알고리즘으로 매우 빠르며, 대용량 데이터에서 특정 값을 빠르게 찾을 때 유용합니다.

일반적으로 이진 탐색법을 사용하여 원하는 요소의 인덱스를 반환하는 코드는 다음과 같습니다.

public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // 원하는 요소를 찾은 경우 해당 인덱스를 반환
            } else if (arr[mid] < target) {
                left = mid + 1; // 중간 값보다 큰 경우 오른쪽 반을 탐색
            } else {
                right = mid - 1; // 중간 값보다 작은 경우 왼쪽 반을 탐색
            }
        }

        return -1; // 원하는 요소가 배열에 없는 경우 -1을 반환
}

하지만 문제에서는 인덱스의 번호가 아닌 횟수를 구해야 합니다.

원하는 요소의 개수를 이진 탐색을 사용하여 구하려면 일반적으로 배열이 정렬되어 있어야 합니다. 왜냐하면 정렬되지 않은 배열에서 원하는 요소의 개수를 구하려면 배열 전체를 순회해야 하지만, 정렬된 배열에서는 이진 탐색을 사용하여 효율적으로 개수를 계산할 수 있습니다.

이진탐색을 사용하여 배열에서 원하는 요소의 첫번째 등장과 마지막 등장 인덱스를 찾아 계산하면 원하는 요소의 개수가 나옵니다.

findFirstOccurrence 메서드:

• 이진 탐색을 사용하여 정렬된 배열 arr에서 target 값의 첫 번째 등장 인덱스를 찾습니다.
• left와 right라는 두 개의 포인터를 사용하여 배열을 탐색합니다.
• 반복문을 통해 left가 right보다 작거나 같을 때까지 탐색을 수행합니다.
• 중간 인덱스 mid를 계산하고, arr[mid]와 target를 비교합니다.
• arr[mid]가 target와 같다면, mid를 firstOccurrence에 저장하고, 더 왼쪽 부분에서도 같은 요소가 있는지 탐색하기 위해 right를 mid - 1로 업데이트합니다.
• arr[mid]가 target보다 작다면, left를 mid + 1로 업데이트하여 오른쪽 부분을 탐색합니다.
• arr[mid]가 target보다 크다면, right를 mid - 1로 업데이트하여 왼쪽 부분을 탐색합니다.
• 반복문을 빠져나왔을 때, firstOccurrence에는 첫 번째 등장 인덱스가 저장되어 반환됩니다.

findLastOccurrence 메서드:

• 이진 탐색을 사용하여 정렬된 배열 arr에서 target 값의 마지막 등장 인덱스를 찾습니다.
• 구조와 동작은 findFirstOccurrence와 유사하지만, 중간 인덱스 mid에서 arr[mid]와 target를 비교하여 오른쪽 부분을 탐색하며, lastOccurrence에 마지막 등장 인덱스를 저장합니다.

이진 탐색법에 대한 이해를 한번만 잘 하면 얼마든지 응용하여 풀 수 있는 문제였습니다.