공부 223일차: 백준 10815번 숫자 카드 자바 java

10815 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

 

 

---

백준 10815번 문제 숫자 카드

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	75412	34280	24611	44.488%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

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

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

제한

 

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

가볍게 정리해본 이진 탐색

https://gimbalja.tistory.com/388

이분 탐색 이진 탐색(Binary Search)

 

기본적인 이진 탐색 문제

이 블로그를 참고했다

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n;
    static int[] card;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        card = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(card);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            bw.write(binarySearch(num)+" ");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
    
    static int binarySearch(int num) {
        int lo = 0;
        int hi = n-1;
        int mid = 0;
        
        while(lo <= hi) {
            mid = (lo+hi)/2;
 
            if(card[mid] == num) {    // 경계에 걸림
                return 1;
            }
            
            if(card[mid] < num) {    // 중간보다 큼 -> 그 윗값들만 확인
                lo = mid + 1;
            }else {
                hi = mid - 1;
            }
        }
        return 0;
    }
 
}
 

 

 

 

---

오늘 컨디션이 왜 이렇게 안 좋지 머리 아파서 이해하는 데 오래 걸렸다