[BAEKJOON] - 10815번 : 숫자 카드

10815번 문제 링크

⌛ 시간 복잡도

• N : 500,000 / M : 500,000 / 2초
• 2 10^8 25 10^10 (O(N^2)) X
• 따라서 O(NlogN) 이하의 알고리즘으로 구현
• 정렬부분 - O(NlogN) + 이진 탐색 부분 - O(MlogN)

📜 로직

위 문제는 전일 풀었던 이분탐색을 이용한 타겟 데이터의 존재 여부를 확인하는 간단한 문제였습니다.

• N개의 배열을 오름차순으로 정렬해줍니다.
• 중간 index 설정 후, target 데이터가 중간값 보다 큰지, 작은지 판별하여 왼쪽셋 또는 오른쪽셋으로 이분할 하여 탐색을 수행해줍니다.
• 중간값이 target 데이터가 같으면 1, 아닌 경우 0을 출력해줍니다.

😀 성공

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

public class Main{
    static int n;
    static int[] a;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        
        a = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i < n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        
        br.close();
        
        for(int i=0; i < m; i++){
            int target = Integer.parseInt(st.nextToken());
            
            if(binarySearch(target)){
                sb.append(1).append(" ");
            }else{
                sb.append(0).append(" ");
            }
        }
        
        sb.deleteCharAt(sb.length() - 1);
        
        System.out.println(sb);
    }
    
    static boolean binarySearch(int target){
        int start = 0;
        int end = n - 1;
        
        if(target < a[start] || target > a[end]){
            return false;
        }
        
        while(start <= end){
            int middle = (start + end) / 2;
            
            if(target < a[middle]){
                end = middle - 1;
            }
            else if(target > a[middle]){
                start = middle + 1;
            }
            else{
                return true;
            }
        }
        
        return false;
    }
}