99클럽 코테 스터디 14일차 TIL - [백준] 숫자 카드2 (Java)

📌 오늘의 학습 키워드

[백준] 숫자 카드2 (Java)
https://www.acmicpc.net/problem/10816

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 첫째 줄 - 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)
둘째 줄 - 숫자 카드에 적혀있는 수 n[N] (-10,000,000 ≤ n[N] ≤ 10,000,000)
셋째 줄 - 가지고 있는 숫자 카드인지 구해야 할 정수 M (1 ≤ M ≤ 500,000)
넷째 줄 - 숫자 카드에 적혀있는 수 m[M] (-10,000,000 ≤ m[M] ≤ 10,000,000)
출력 : M개의 정수가 N개의 정수 안에 존재하면 1, 존재하지 않으면 0분

가능한 시간복잡도

O(nlogn)

알고리즘 선택

정렬, 이진 탐색

📌 코드 설계하기

1. N, n 배열을 input으로 받는다.
2. 이진탐색을 하기 위해 n 배열을 정렬한다.
3. M, m 배열을 input으로 받는다.
4. lowerBound 함수를 통해 arr에서 key 보다 크거나 같은 첫 번째 위치를 찾는다.
5. upperBound 함수를 통해 arr에서 key 보다 큰 첫 번째 위치를 찾는다.
6. m 배열에 대해 n 배열 안의 값의 빈도를 계산해 StringBuilder에 추가한다.
7. StringBuilder를 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

Arrays.binarySearch를 사용했더니 시간초과가 발생했다.

어떻게 해결했는지

lowerBound, upperBound 함수를 설계했다.
출력할때는 시간을 줄이고자 StringBuilder로 사용해 바꿨다.

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        int N = sc.nextInt();
        int[] n = new int[N];
        for (int i=0; i<N; i++) {
            n[i] = sc.nextInt();
        }
        Arrays.sort(n); //이진탐색을 위한 정렬
        
        int M = sc.nextInt();
        int[] m = new int[M];
        for (int i=0; i<M; i++) {
            m[i] = sc.nextInt();
            sb.append(upperBound(n, m[i]) - lowerBound(n, m[i])).append(" ");
        }
        System.out.println(sb);
    }
    
    public static int lowerBound(int[] arr, int key) {
        int low = 0;
        int high = arr.length;
        
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    
    public static int upperBound(int[] arr, int key) {
        int low = 0;
        int high = arr.length;
        
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] <= key) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}