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

 

10816번: 숫자 카드 2

 

이전에 해결한 백준 1920번 수 찾기와 유사한 문제이다.

1920번: 수 찾기

 

 

이분 탐색으로 특정 숫자의 존재 유무를 확인하는 이전 문제와 동일한 논리를 적용하되, 차이점은 이번 문제에서는 가지고 있는 특정 숫자 카드의 갯수를 출력해야 한다는 부분이다.

 

 

문제를 해결하기 위해 lowerBound와 upperBound를 각각 찾아서 두 반환 값의 차이를 출력하는 방법을 사용하였다. 문제에 따라 lowerBound와 uppperBound가 반환하는 값을 다르게 설계할 수 있겠으나, 내가 푼 풀이에서는 lowerBound는 주어진 오름차순으로 정렬된 수열에서 내가 찾고자 하는 수보다 '같거나 큰 값'이 처음 나오는 인덱스를 반환하고 upperBound는 주어진 오름차순으로 정렬된 수열에서 내가 찾고자 하는 수보다 '큰' 값이 처음 나오는 인덱스를 반환한다.

 

lowerBound와 upperBound의 차이점은 현재 탐색 범위의 중간값인 A[mid]가 key와 같은 경우 다음 탐색 범위를 어떻게 줄일 것인지에 있다.

lowerBound와 upperBound 모두 A[mid] < key 라면 left = mid + 1 해준다. 그러고 lowerBound의 경우 A[mid] = key라면 right = mid를 해줌으로써 숫자 카드 내에 여러개 존재하는 key들 중 가장 먼저 나오는 인덱스를 반환할 수 있게 된다. 반대로 upperBound의 경우 A[mid] = key라면 left = mid + 1;을 해줌으로써 주어진 숫자 카드들 중에서 처음으로 key보다 큰 값이 나오는 인덱스를 반환할 수 있게 된다.

static int lowerBound (int key) {
        
    int left = 0;
    int right = N;

    while (left < right) {

        int mid = (left + right) / 2;

        if (A[mid] >= key) right = mid;
        else left = mid + 1;
    }

    return left;
}

static int upperBound (int key) {

    int left = 0;
    int right = N;

    while (left < right) {

        int mid = (left + right) / 2;

        if (A[mid] > key) right = mid;
        else left = mid + 1;
    }

    return left;
}

 

 

 

 

주어진 예제의 수열을 오름차순 정렬하면 다음과 같다.

-10 -10 2 3 3 6 7 10 10 10

 

만약 숫자 카드 10이 몇 개 존재하는지 알아보고자 한다면, lowerBound에 의해 숫자 10보다 같거나 큰 값이 처음 나오는 인덱스인 7이 return될 것이고, upperBound에 의해 숫자 10 보다 큰 값이 처음 나오는 인덱스인 10이 return 될 것이다.

따라서 upperBound - lowerBound = 3이 출력된다.

이와 반대로 숫자 카드 내에 없는 숫자인 9의 갯수를 확인하는 과정을 살펴보자. lowerBound에 의해 숫자 9보다 같거나 큰 값이 처음 나오는 인덱스는 7이다. 그리고 upperBound에 의해 숫자 9보다 큰 값이 처음 나오는 인덱스 또한 7이다.

따라서 upperBound - lowerBound = 0이 출력된다.

 

여기서 처음 탐색을 시작할 때에 right 값을 이전에 N-1을 주었던 것과는 달리 N을 주었는데, 이는 반복문이 left < right 인 경우에 반복을 하기 때문에 left = right인 경우에는 탐색을 종료한다. 따라서 초기에 right = N-1로 값을 설정하면 주어진 숫자카드 수열의 마지막 카드에 대해서는 내가 찾는 카드인지 아닌지 체크하지 않고 종료되어 버리기 때문에 right = N이라고 값을 주었다.

 

 

 

전체 코드

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

public class Main {
    
    static int N, M, A[];
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(A);
        
        
        M = Integer.parseInt(br.readLine());
        int[] B = new int[M];
        
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<M; i++) B[i] = Integer.parseInt(st.nextToken());
        
        
        for (int i=0; i<M; i++) {
            
            // 정수 M 개에 대하여, 이 숫자 카드를 몇 개 가지고 있는지 확인
            int key = B[i];
            
            sb.append((upperBound(key) - lowerBound(key)) + " ");
        }
        
        System.out.println(sb);
        
        br.close();
    }    
    
    static int lowerBound (int key) {
        
        int left = 0;
        int right = N;
        
        while (left < right) {
            
            int mid = (left + right) / 2;
            
            // lowerBound는 수열 A에서 key보다 처음 같거나 큰 값의 인덱스를 반환하므로 A[mid] >= key 인 경우 right = mid
            if (A[mid] >= key) right = mid;
            else left = mid + 1;
        }
        
        return left;
    }
    
    static int upperBound (int key) {
        
        int left = 0;
        int right = N;
        
        while (left < right) {
            
            int mid = (left + right) / 2;
            
            // upperBound는 수열 A에서 key보다 처음 커지는 값의 인덱스를 반환하므로 A[mid] > key 인 경우 right = mid
            if (A[mid] > key) right = mid;
            else left = mid + 1;
        }
        
        return left;
    }
}