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

문제

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

---

수도코드 작성

사실 이건 전에 푼 1920번 문제하고 비슷하게 풀면 된다고 생각을 했다.. 하지만 안풀려서 수도코드를 세우지 않았다...

---

작성한 코드

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

public class test01 {
    public static void main(String[] args) {
        // 입력문
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder(); // 최대한 시간을 줄이기위해 StringBuilder사용

        int N = sc.nextInt();
        int[] A = new int[N];

        for (int i = 0; i < A.length; i++) {
            A[i] = sc.nextInt();
        }

        int M = sc.nextInt();

        Arrays.sort(A); // 이진탐색은 정렬 후에 사용해야 하므로 선정렬

        for (int i = 0; i < M; i++) {
            int target = sc.nextInt();
                sb.append(upperBound(A, target) - lowerBound(A, target)).append(" ");
        }
        System.out.println(sb);

    }
    public static int upperBound(int[] arr, int target){
        int left = 0;
        int right = arr.length;
        while(left<right){
            int mid = (left+right)/2;
            if(target < arr[mid]){
                right = mid;
            }else left=mid + 1;
        }
        return left;
    }
    public static int lowerBound(int[] arr, int target){
        int left = 0;
        int right = arr.length;
        while(left<right){
            int mid = (left+right)/2;
            if(arr[mid]>=target){
                right = mid;
            }else left = mid + 1;
        }
        return left;
    }
}

---

보완할 점 / 헷갈린 점

처음에는 upperBound와 lowerBound의 개념이 없는 상태로 문제를 풀어서 기본적인 이진탐색함수를 만든 후 거기서 중복되는 갯수를 세면 된다고 생각을 했다. 그래서 이진탐색함수를 사용해 중복을 찾을 때 마다 count++ 이 되게 만들었는데 이게 문제점이 while문을 계속 돌리면 중복이 발생해서 count++ 된건지 그냥 발견해서 된건지 모르니까 문제가 발생하였다.
중복을 제거하면서 문제를 풀어도 풀릴지는 모르겠는데 계속 고민하던 중에 검색을 통해 찾아낸게 upperBound와 lowerBound의 개념이였다. 이진탐색 문제를 풀면서 응용되는 것들을 다 정리해서 한번에 블로그에 올려야겠다.