반응형
12-24 07:02
Today
Total
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
관리 메뉴

개발하는 고라니

[백준] 10815번 : 숫자 카드 본문

Programming/백준

[백준] 10815번 : 숫자 카드

조용한고라니 2021. 3. 12. 19:20
반응형
 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net


[이진 탐색, Binary Search]

그래프 문제를 주로 풀다가 문제의 스펙트럼을 좀 넓혀보고자 이진 탐색 문제를 풀기로 하였다. 이진 탐색의 기본적인 내용을 다루며 응용에 힘쓰도록 한다.

 

이 문제는 교과서적인 이진 탐색을 물어보는 문제이고, m개의 데이터에 대해 이진 탐색을 수행하면 되므로 딱히 어려울 것은 없어보인다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] num = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            num[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(num);

        int m = Integer.parseInt(br.readLine());
        boolean[] result = new boolean[m];

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

            int left = 0, right = n-1;
            while(left <= right){

                int mid = (left + right) / 2;

                if(num[mid] >= target) {
                    if (num[mid] == target)
                        result[i] = true;

                    right = mid - 1;
                }
                else
                    left = mid + 1;
            }
            System.out.print(result[i]?"1 " : "0 ");
        }
    }
}
반응형

'Programming > 백준' 카테고리의 다른 글

[백준] 10816번 : 숫자 카드 2  (0) 2021.03.13
[백준] 1654번 : 랜선 자르기  (0) 2021.03.13
[백준] 1963번 : 소수 경로  (0) 2021.03.12
[백준] 16946번 : 벽 부수고 이동하기 4  (0) 2021.03.10
[백준] 9328번 : 열쇠  (0) 2021.03.09
Comments