[백준] 10815. 숫자 카드

링크

[백준] 10815. 숫자 카드

풀이 과정

HashSet 과 이분 탐색 을 이용해 문제를 풀었습니다.

HashSet

while (st.hasMoreTokens()) {
    hashSet.add(Integer.parseInt(st.nextToken()));
}

hashSet 에 N개의 카드를 집어 넣습니다. add 메소드 는 O(1)의 상수 시간 시간 복잡도를 갖습니다.

while (st.hasMoreTokens()) {
    if (hashSet.contains(Integer.parseInt(st.nextToken()))) answer.append("1 ");
    else answer.append("0 ");
}

M개의 카드를 입력받음과 동시에 hashSet 에서 그 카드가 있나 찾아봅니다. contains 메소드 도 add 와 같이 O(1)의 시간 복잡도를 갖습니다.

이분 탐색

int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

N개의 카드들 정보를 한 줄로 입력받아 int[] 배열로 변환합니다.

Arrays.sort(nums);

이후, 이분 탐색의 양 끝 low 와 high 를 판별하기 위해 오름차순 정렬해줍니다.

while (st.hasMoreTokens()) {
    int target = Integer.parseInt(st.nextToken());
    int low = 0, high = nums.length - 1;
    boolean find = false;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (target > nums[mid]) {
            low = mid + 1;
        } else if (target < nums[mid]) {
            high = mid - 1;
        } else {
            find = true;
            break;
        }
    }

    if (find) answer.append("1 ");
    else answer.append("0 ");
}

M개의 카드 각각에 대해 이분 탐색을 실행합니다.

---

이 문제는 HashSet을 사용하는게 이분 탐색보다 실행 시간이 빠릅니다.

• HashSet의 경우, 각 카드에 대해 contains 메소드를 실행하는 O(1)의 시간이 소요됩니다.
• 이분 탐색의 경우, 정렬하는 데에 걸리는 시간에 더해, 각 카드에 대해 이분 탐색을 진행하는 O(logM)의 시간이 추가로 소요됩니다.

코드

HashSet

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<Integer> hashSet = new HashSet<>();

        while (st.hasMoreTokens()) {
            hashSet.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder answer = new StringBuilder();

        while (st.hasMoreTokens()) {
            if (hashSet.contains(Integer.parseInt(st.nextToken()))) answer.append("1 ");
            else answer.append("0 ");
        }

        System.out.println(answer);
    }
}

이분 탐색

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[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder answer = new StringBuilder();
        Arrays.sort(nums);

        while (st.hasMoreTokens()) {
            int target = Integer.parseInt(st.nextToken());
            int low = 0, high = nums.length - 1;
            boolean find = false;

            while (low <= high) {
                int mid = (low + high) / 2;

                if (target > nums[mid]) {
                    low = mid + 1;
                } else if (target < nums[mid]) {
                    high = mid - 1;
                } else {
                    find = true;
                    break;
                }
            }

            if (find) answer.append("1 ");
            else answer.append("0 ");
        }

        System.out.println(answer);
    }
}