[백준] 10815 : 숫자 카드 / python

1. 문제 설명

문제

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

 

2. 풀이 전 계획과 생각

• 상근이가 가지고 있는 숫자 카드 → 배열
• 상근이가 가지고 있는 숫자 카드인지 아닌지 구해야 할 M개의 정수 → 배열

 

각각의 숫자가 상근이가 가지고 있는지 확인하려면

배열을 정렬하고 일일히 순차적으로 탐색하기보다

배열을 정렬하되, 이진탐색으로 탐색하자.

 

 

🤔 숫자카드의 갯수가 많음으로 배열 대신 heap을 사용하여, 정렬하자.

1. heap으로 정렬
2. 숫자카드 있는지 없는지 이진탐색

 

✋🏻  새로운 값이 추가되어 그때마다 정렬하는 것이 아니라, 정렬은 한번만 해주면 되니까

       heap 사용할 필요가 없다!

 

3. 풀이

import sys

input = sys.stdin.readline
N = int(input())
number_card = sorted(list(map(int, input().split())))
M = int(input())
cards = list(map(int, input().split()))

def check_card(card):
    left = 0
    right = N-1
    while left <= right:
        mid = (left + right) // 2
        if number_card[mid] == card:
            return 1
        elif card < number_card[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return 0

for card in cards:
    print(check_card(card), end= " ")

 

4. 다른 풀이

import sys

input = sys.stdin.readline
N = int(input())
number_card = sorted(list(map(int, input().split())))
M = int(input())
cards = list(map(int, input().split()))

dict = {}
for card in number_card:
    if card in number_card:
        hashmap[card] += 1
    else:
        hashmap[card] = 1

for card in cards:
    if card in dict:
        print(1, end=" ")
    else:
        print(0, end=" ")

해시테이블은 시간복잡도가 O(1)이여서 탐색을 빠르게 할 수 있다.

🤔  Why?

각각의 Key 값은 해쉬함수에 의해 고유한 Index를 가지게 되어 바로 접근할 수 있음으로,

평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.

 

5. 풀이 후 알게된 개념

• 입력된 배열 이분탐색을 하는데 꼭 정렬해주자!
• 부등호 잘 쓰자!
• left, right 범위 설정 잘 했는지 확인해주자!