[백준] 1920번 - 수 찾기 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 $N$ 개의 정수에 대해 이 안에 $X$ 가 존재하는지 여부를 찾는 문제다. 주어진 수의 범위가 너무 커서 방문 체크 배열을 활용해서는 풀 수 없다. 주어진 수를 정렬한 후 이분 탐색을 통해 찾던가 집합을 활용해서 포함 여부를 판단하는 방식으로 해결할 수 있다.

---

2. 코드

1. 이분 탐색 [Java]

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();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] 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);

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            if (Arrays.binarySearch(arr, Integer.parseInt(st.nextToken())) >= 0) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        System.out.println(sb);
    }
}

2. 해시를 사용한 집합과 맵 [Java]

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();
        StringTokenizer st;

        Set<Integer> set = new HashSet<>();

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            set.add(Integer.parseInt(st.nextToken()));
        }

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            if (set.contains(Integer.parseInt(st.nextToken()))) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        System.out.println(sb);
    }
}

3. 이분 탐색 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;
    sort(v.begin(), v.end());

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;

        if (binary_search(v.begin(), v.end(), x)) {
            cout << 1 << '\n';
        } else {
            cout << 0 << '\n';
        }
    }
}

4. 해시를 사용한 집합과 맵 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    unordered_set<int> st;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        st.insert(x);
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;

        if (st.count(x)) {
            cout << 1 << '\n';
        } else {
            cout << 0 << '\n';
        }
    }
}

---

3. 풀이 정보

1. 이분 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	660 ms	42896 KB	889 B

2. 해시를 사용한 집합과 맵 [Java]

언어	시간	메모리	코드 길이
Java 11	512 ms	49576 KB	831 B

3. 이분 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	48 ms	2412 KB	469 B

4. 해시를 사용한 집합과 맵 [C++]

언어	시간	메모리	코드 길이
C++ 17	64 ms	6820 KB	484 B

---