[백준] 10815번 : 숫자 카드

김건우·2023년 7월 11일
0

문제 풀이

목록 보기
7/62

숫자 카드


해결 방법

완전 탐색을 통해 해결하려고 하면 최대 (500,000 * 20,000,000)번 탐색을 하게된다.
이 경우 시간 초과가 일어나기 때문에 이분탐색을 사용해서 해결하는 것이 대표적이다.

조심할 부분은 이분탐색 시에는 반드시 정렬이 되어 있어야 한다는 점이다.

이분탐색 문제에서도 기초 문제여서 간단하게 해결할 수 있었다.


코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] numCard = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++){
            numCard[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(numCard);

        int m = Integer.parseInt(br.readLine());
        int[] checkCard = new int[m];
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<m;i++){
            checkCard[i] = Integer.parseInt(st.nextToken());

            sb.append(binarySearch(checkCard[i],0,n-1,numCard)).append(" ");
        }
        System.out.println(sb);
    }
    public static int binarySearch(int m,int min,int max,int[] arr){
        while(min<=max){
            int mid = (min+max)/2;
            if(arr[mid]==m){
                return 1;
            }
            else if(m<arr[mid]){
                max = mid-1;
            }
            else{
                min = mid+1;
            }
        }
        return 0;
    }
}
profile
공부 정리용

0개의 댓글