[Baekjoon] 10815 - 숫자 카드

📝 문제

 

 

🔑 풀이 과정

· 주어진 시간은 2초. 약 2억번 연산. N과 M의 최댓값이 5 * 10^5 이므로

일반적인 for문을 사용한 완전탐색 사용시, 최악의 경우 2.5 * 10^10 번 연산이 나오므로 사용할 수 없다. 

그래서 일반탐색 대신 이분탐색을 사용할 것.

 

· 이분탐색은 기본적으로 정렬이 되어있는 상태에서 가능하다. 꼭! 배열을 입력받은뒤 정렬을 해주자.

 

· 처음 작성했던 코드가 이분탐색 부분에서 while(start < end) 라고 조건을 적었는데,

이럴 경우 start == end 인 경우 반복문이 작동하지 않게 된다. 조건은 while(start <= end)로 적어주자.

 

 

 

 

🔓 답안

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //숫자 카드 입력 받기
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        //찾아야 하는 수 입력 받기, 검사 후 결과 출력
        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            int num = Integer.parseInt(st.nextToken());

            if(binarySearch(num))
                bw.write("1 ");
            else
                bw.write("0 ");
        }

        bw.flush();
        bw.close();
    }

    //이진탐색 메서드. 찾는수(num)이 arr 배열에 존재하면 true 반환
    static boolean binarySearch(int num){
        int start = 0;
        int end = N-1;
        int middle = (start + end) / 2;

        boolean isExist = false;
        while(start <= end){
            if(num == arr[middle]){
                isExist = true;
                break;
            } else if(num < arr[middle]){
                end = middle - 1;
                middle = (start + end) / 2;
            } else if(num > arr[middle]){
                start = middle + 1;
                middle = (start + end) / 2;
            }
        }

        return isExist;
    }

}

 

 

 

🖤 알고리즘 분류

- 자료 구조

- 정렬

- 이분 탐색