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

📌 오늘의 학습 키워드

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

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

문제 탐색하기

입력 : 첫째 줄 - 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)
둘째 줄 - 숫자 카드에 적혀있는 정수
셋째 줄 - 확인할 숫자 카드의 개수 M (1 ≤ M ≤ 500,000)
넷째 줄 - 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수
출력 : 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분

가능한 시간복잡도

O(nlogn)

알고리즘 선택

정렬, 이진 탐색

📌 코드 설계하기

1. 상근이가 가지고 있는 숫자 카드의 개수를 입력 받고, 그 숫자 카드들을 배열에 저장한다.
2. 이진 탐색을 수행하기 위해 상근이의 숫자 카드 배열을 오름차순으로 정렬한다.
3. 확인할 숫자 카드의 개수를 입력 받고, 각 숫자 카드가 상근이의 숫자 카드 배열에 존재하는지를 확인한다.
4. binarySearch 메소드를 통해 숫자가 배열에 존재하는지를 확인하고, 결과를 StringBuilder에 모아 마지막에 출력한다.

📌 오늘의 회고

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

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 첫 번째 줄: 상근이가 가지고 있는 숫자 카드의 개수
        int n = scanner.nextInt();
        int[] sanggeunCards = new int[n];
        
        // 상근이가 가지고 있는 숫자 카드 입력
        for (int i = 0; i < n; i++) {
            sanggeunCards[i] = scanner.nextInt();
        }
        
        // 숫자 카드 정렬
        Arrays.sort(sanggeunCards);
        
        // 두 번째 줄: 확인할 숫자 카드의 개수
        int m = scanner.nextInt();
        int[] queryCards = new int[m];
        
        // 확인할 숫자 카드 입력
        for (int i = 0; i < m; i++) {
            queryCards[i] = scanner.nextInt();
        }
        
        StringBuilder result = new StringBuilder();
        
        // 각 숫자가 상근이의 숫자 카드에 있는지 확인
        for (int i = 0; i < m; i++) {
            if (binarySearch(sanggeunCards, queryCards[i])) {
                result.append("1 ");
            } else {
                result.append("0 ");
            }
        }
        
        // 결과 출력
        System.out.println(result.toString().trim());
        
        scanner.close();
    }
    
    // 이진 탐색을 이용하여 숫자가 배열에 있는지 확인
    private static boolean binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == key) {
                return true;
            } else if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}