[백준 10815번] 숫자 카드 파이썬 풀이

숫자 카드

2 초

256 MB

102414

43067

31537

42.773%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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 0 1 1 0 0 1

이분탐색(이진탐색)을 이용하여 해결할수 있는 문제이다.

 

이분탐색은 탐색의 범위를 절반씩 좁혀나가면서 원하는 데이터가 존재하는지 탐색한다.

이분탐색을 적용하면 모든 요소를 하나씩 탐색하는 순차탐색보다 빠른 속도로 데이터를 탐색할 수 있기 때문에 탐색할 범위가 크다면, 순차탐색보다 이분탐색을 적용하는것이 좋다. 위 문제의 경우 탐색의 범위가 최대 50만까지 가능하므로 이분탐색을 적용하여 풀었다.

 

이분탐색에 대해 이해하고 있다면, 별도의 해설이 가능하지 않으므로 별도의 해설은 적지 않겠다.

# 카드의 개수 입력받기
n = int(input())

# 카드 리스트 입력받기
card_list = list(map(int, input().split()))

# 탐색할 카드의 개수 입력받기
m = int(input())

# 탐색할 카드 리스트 입력받기
search_list = list(map(int, input().split()))

# 이분 탐색을 이용하기 위해 카드리스트를 정렬한다.
card_list.sort()

for i in range(len(search_list)):
    # 탐색할 가드 선정
    card = search_list[i]

    # 이분탐색 시작
    start = 0  # 시작 인덱스
    end = len(card_list)  # 마지막 인덱스

    for j in range(start, end):

        # 탐색 종료 조건 설정
        if start >= end:
            # 탐색 실패
            search_list[i] = 0
            break

        # 가운데 인덱스 선택
        middle = (start+end)//2

        # 가운데 값이 탐색카드와 같을때 => 탐색종료
        if card == card_list[middle]:
            # 탐색 성공
            search_list[i] = 1
            break
        # 가운데 카드보다 탐색카드가 클때
        elif card > card_list[middle]:
            # 탐색 범위 수정
            start = middle+1

        # 가운데 카드보다 탐색카드가 작을때
        elif card < card_list[middle]:
            end = middle


# 탐색 결과 출력
for card in search_list:
    print(card, end=" ")

 

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

10815번: 숫자 카드