[백준 10815] 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

---

🤔 주의할점

• 이분탐색
• 브루트 포스로 할 경우 50만 * 50만으로 시간제한에 걸림.

---

🎯 풀이

• BufferedReader와 BufferedWriter를 활용해 입출력 시간 단축.
• 카드를 정렬한 후 찾는 카드에 대해 이분탐색 수행

---

📌 코드

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

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

        int n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        StringTokenizer 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 target = Integer.parseInt(st.nextToken());
            boolean find = false;
            int start = 0;
            int end = n - 1;
            while (start <= end) {
                int mid = (start + end) / 2;
                if (arr[mid] == target) {
                    bw.write("1 ");
                    find = true;
                    break;
                }
                else if (arr[mid] > target) {
                    end = mid - 1;
                }
                else {
                    start = mid + 1;
                }
            }
            if (find == false) bw.write("0 ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

---

💡알게된 것

• readLine()은 next()와 비슷하게 입력 전체를 읽어 문자열로 저장한다.
• 문자열 가공시 String.split이나 StringTokenizer를 주로 사용.
• nextToken() 함수로 다음 토큰값을 불러올 수 있는데. 이 때 반환값은 String이다.
• BufferedWriter는 반드시 flush()로 버퍼를 비운 뒤 close()를 호출해 닫아주어야한다.