백준 10816 : 숫자 카드 2 [JAVA]

https://www.acmicpc.net/problem/10816

 

[난이도]

- Silver 4

 

[알고리즘]

- 이분탐색

 

[코드]

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

public class Main {
    static int N, M;
    static int[] arr, answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        M = Integer.parseInt(br.readLine());
        answer = new int[M];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            int tmp = upperBound(key) - lowerBound(key);
            bw.write(tmp + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    /**
     * key 값이 배열 내에 없을 경우 lowerBound, upperBound 둘다 key 바로 앞의 숫자를 찾게된다. 결국 n - n = 0이 된다.
     */

    static int lowerBound(int key) {
        int left = 0;
        int right = N;
        while (left < right) { // left 와 right가 같아질 때 까지 반복
            int mid = (left + right) / 2; // 중간 위치

            /**
             * key 값이 중간 위치의 값보다 작거나 같을 경우
             * 중복 원소일 경우 가장 왼쪽값을 선택
             */
            if (key <= arr[mid]) {
                right = mid;
            } else { // key가 중간 값보다 '클' 경우. key > arr[mid]
                left = mid + 1;
            }
        }
        return left;
    }

    static int upperBound(int key) {
        int left = 0;
        int right = N;
        while (left < right) {// left 와 right가 같아질 때 까지 반복
            int mid = (left + right) / 2; // 중간 위치
            if (key < arr[mid]) { // key가 중간 값보다 작을 경우
                right = mid;
            } else { // key가 중간 보다 '크거나' '같을' 경우 key >= arr[mid]
                left = mid + 1;
            }
            // left가 right를 넘어서는 순간 종료된다 == left가 key의 바로 다음 인덱스가 되는순간 종료된다.
        }
        return left;
    }
}

[풀이]

배열안에 중복값이 들어있을 경우가 존재하기 때문에 그 ( 중복값의 가장 왼쪽 인덱스 - 중복값의 가장 오른쪽의 다음 인덱스 ) 를 계산해주어야 한다.

 

leftBound

찾으려는 key값이 중간 값보다 작거나 클 경우 right 값이 mid가 되고 그 이외의 경우에는 left = mid + 1이 된다.  이를 반복할 경우 left 와 right가 key값들의 가장 왼쪽인덱스가 된다.

 

rightBound

찾으려는 key값이 중간 값보다 작을 경우 right = mid가 되고 그 외의 경우에는 left = mid + 1이 된다. 이를 반복하다 보면 right는 key값들의 가장 오른쪽 인덱스, left는 key값들의 가장 오른쪽의 다음 인덱스가 된다.

 

만약 찾으려는숫자가 없을 경우 lowerBound, upperBound 둘다 배열 중 key값을 초과하는 값중 첫 인덱스를 가리키게 된다.

 

 

[출처]

https://st-lab.tistory.com/267