백준 숫자 카드(10815)

백준에서 보이는 이분 탐색 문제 하나를 선택했다.

 

 

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

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을 공백으로 구분해 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

1 0 

 

 

문제 풀이

상근이의 N개의 카드에서 M개의 타겟을 조회하여 존재 여부를 파악하는 문제다.

 

문제를 어떻게 풀어야할까 생각하니 아래와 같이 정리가 되었다.

1. 카드 리스트를 어떻게 관리할까?

2. 타겟을 어떻게 조회할까?

 

처음에는 정리한 알고리즘인 이분 탐색으로 생각했다. 

카드 리스트를 정리하고 그 다음에 타겟 리스틀 이분탐색으로 조회하는 방식으로 풀이했다.

 

그런데 다시 생각해보니 그냥 해시로 관리하면 되는거 아닌가 해서 풀어보니 두가지 방식으로 다풀렸다..

 

package binarySearch;

import java.util.*;
import java.util.stream.Collectors;

/**
 * https://www.acmicpc.net/problem/10815
 */
public class Q10815 {

    public static void main(String[] args) {
//        binarySearch();
        hashTable();
    }

    public static void binarySearch() {
        Scanner sc = new Scanner(System.in);
        List<Integer> answer = new ArrayList<>();
        int n = Integer.parseInt(sc.nextLine());
        List<Integer> cards = Arrays.stream(sc.nextLine().split(" ")).map(it -> Integer.parseInt(it)).sorted().collect(Collectors.toList());
        int m = Integer.parseInt(sc.nextLine());
        Arrays.stream(sc.nextLine().split(" ")).map(it -> Integer.parseInt(it)).collect(Collectors.toList())
                .forEach(it -> answer.add(isExist(cards,0, n - 1, it) ? 1: 0)); // 구분 카드 리스트 이분 탐색
        System.out.println(answer.stream().map(it -> it + " ").collect(Collectors.joining()).trim());
    }

    public static boolean isExist(List<Integer> cards, int start, int end, int target) {
        if (start > end) return false; // 크기가 역순이 되면 조회 실패

        int mid = (start + end) / 2; // 중간 값

        if (cards.get(mid) == target) { // 성공
            return true;
        } else if (cards.get(mid) < target) { // 시작점을 중간점 + 1
            return isExist(cards, mid + 1, end, target);
        } else { // 종료점을 중간점 - 1
            return isExist(cards, start, mid - 1, target);
        }

    }

    public static void hashTable() {
        Scanner sc = new Scanner(System.in);
        List<Integer> answer = new ArrayList<>();
        HashSet<Integer> hashSet = new HashSet<>();
        int n = Integer.parseInt(sc.nextLine());
        List<Integer> cards = Arrays.stream(sc.nextLine().split(" ")).map(it -> Integer.parseInt(it)).collect(Collectors.toList());
        cards.stream().forEach(it -> hashSet.add(it));
        int m = Integer.parseInt(sc.nextLine());
        Arrays.stream(sc.nextLine().split(" ")).map(it -> Integer.parseInt(it)).collect(Collectors.toList())
                .forEach(it -> answer.add(hashSet.contains(it) ? 1 : 0)); // 구분 카드 리스트 이분 탐색
        System.out.println(answer.stream().map(it -> it + " ").collect(Collectors.joining()).trim());
    }


}

 

 

Binary Search 결과

 

Hash 결과