[백준] 10816번: 숫자 카드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(Nlog N)

알고리즘 선택

이진탐색

📌 코드 설계하기

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

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

Arrays.binarySearch를 사용했더니 시간초과가 발생했다. lowerBound, upperBound 함수를 설계했다.
출력할때는 시간을 줄이고자 StringBuilder로 사용해 바꿨다.

예제 배열

배열 arr = [1, 2, 2, 3, 3, 3, 4, 5]

lowerBound 함수 실행 예제

key = 3
초기 상태: low = 0, high = 8
1차 반복: mid = 4, arr[4] = 3 (key와 같으므로 high = 4)
2차 반복: mid = 2, arr[2] = 2 (key보다 작으므로 low = 3)
3차 반복: mid = 3, arr[3] = 3 (key와 같으므로 high = 3)
종료: low = 3, high = 3 → 반환값: 3

upperBound 함수 실행 예제

key = 3
초기 상태: low = 0, high = 8
1차 반복: mid = 4, arr[4] = 3 (key와 같으므로 low = 5)
2차 반복: mid = 6, arr[6] = 4 (key보다 크므로 high = 6)
3차 반복: mid = 5, arr[5] = 3 (key와 같으므로 low = 6)
종료: low = 6, high = 6 → 반환값: 6
lowerBound와 upperBound 함수를 통해 배열 내 특정 값의 시작과 끝+1 위치를 찾아 빈도를 계산함

2회차

📌 정답 코드

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;
    }
}