알고리즘) 숫자 카드 2(백준 이분탐색 10816번)

문제(백준)

 해당 문제는 K개의 수를 받아서 해당 수들이 M개의 카드 목록에 몇개 존재하는지를 확인해야하는 문제이다. 신경써야 할 부분은 첫 번째로 K번 만큼의 루프를 돌아야 한다는 점, 이분 탐색을 이용하면서 어떻게 특정 수가 몇 개 있는지를 확인하느냐이다.

 특정 수가 몇 개인지 확인하고자 할 때, 우리는 이분 탐색의 특징을 이용할 수 있다. 이분 탐색은 반드시 탐색하는 배열이 정렬되어 있어야 한다. 이를 이용하면 내가 찾고자 하는 값이 탐색하는 배열에 복수개가 있다면, 이들은 연속해서 존재할 것이라는 점이 중요하다. 때문에 연속해서 있는, 이 같은 수들로 이루어진 블럭의 시작과 끝 인덱스를 안다면 해당 요소가 몇 개 있는지 알 수 있다. 이를 위해 UpperBound, LowerBound 개념을 이용한다.

---

cf. 용어 정리

• UpperBound : 찾고자 하는 값을 초과한 값이 처음으로 나타나는 위치
• LowerBound : 찾고자 하는 값 이상이 처음으로 나타나는 위치

예시

---

정렬된 배열에서 특정 수를 탐색할 경우 값의 크기 비교 결과에 따라 탐색 범위를 변경시켜가며 탐색을 마저할 수 있다.  

초기 작성 코드

 해당 코드는 시간 초과 결과가 나왔다..

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private int[] solution(int n, int k, int[] cards, int[] list) {
        int[] result = new int[k];

        Arrays.sort(cards);
        for (int i = 0; i < k; i++) {
            int num = list[i];

            // 가지고 있는 카드 목록(이것을 두 범위로 나누어 확인)의 인덱스를 사용
            int upperBound = getUpperBound(cards, num);
            int lowerBound = getLowerBound(cards, num);
            if (upperBound >= 0 && lowerBound <= n) result[i] = upperBound - lowerBound;
            else result[i] = 0;
        }

        return result;
    }

    private int getUpperBound(int[] arr, int num) {
        int lt = 0;
        int rt = arr.length - 1;
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if(num > arr[mid]) lt = mid + 1;
            else if (num < arr[mid]) rt = mid - 1;
            else {
                lt = mid + 1;
            }
        }
        return lt;
    }

    private int getLowerBound(int[] arr, int num) {
        int lt = 0;
        int rt = arr.length - 1;
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if(num > arr[mid]) lt = mid + 1;
            else if (num < arr[mid]) rt = mid - 1;
            else {
                rt = mid - 1;
            }
        }
        return rt + 1;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] cards = new int[n];
        for (int i = 0; i < n; i++) cards[i] = sc.nextInt();
        int k = sc.nextInt();
        int[] list = new int[k];
        for (int i = 0; i < k; i++) list[i] = sc.nextInt();

        for (int x : main.solution(n, k, cards, list)) System.out.print(x + " ");
    }
}

 

개선 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int getUpperBound(int[] arr, int num) {
        int lt = 0, rt = arr.length - 1;
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if(num >= arr[mid]) lt = mid + 1;
            else rt = mid - 1;
        }
        return lt - 1;
    }

    private static int getLowerBound(int[] arr, int num) {
        int lt = 0, rt = arr.length - 1;
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if (num <= arr[mid]) rt = mid - 1;
            else lt = mid + 1;
        }
        return rt + 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] cards = new int[n];
        for (int i = 0; i < n; i++) cards[i] = sc.nextInt();
        Arrays.sort(cards);

        StringBuilder sb = new StringBuilder();
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int num = sc.nextInt();

            int upperBound = getUpperBound(cards, num);
            int lowerBound = getLowerBound(cards, num);
            sb.append((upperBound - lowerBound + 1) + " ");
        }
        System.out.println(sb.toString());
    }
}

 나름대로 코드를 정돈한다고 해도 계속해서 시간 초과 오류가 발생하는 바람에 아예 main에서 k개의 값을 입력받을 때마다 바로 StringBuilder에 append 해주는 방식으로까지 줄였고.. 드디어 통과했다.... 아마도 k 크기의 배열에 값을 넣는 루프와 기존에 두었던 solution 함수에서의 루프 이 두 가지가 불필요하게 두번 반복되는 것이 이유가 아니었을까...