1 분 소요

[Silver V] 숫자 카드 - 10815

문제 링크

성능 요약

메모리: 113332 KB, 시간: 2096 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 정렬

제출 일자

2024년 5월 2일 17:34:43

문제 설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 존재하지 않으면 0을 반환한다. 접근할 수 있는 방법은 여러가지가 있는데 여기서는 이분 탐색을 이용했다.

이분 탐색을 하기 위해서는 비교할 숫자들이 모두 정렬되어있어야 한다. 따라서 상근이가 가지고 있는 카드들을 리스트에 받은 후 오름차순 정렬을 해주었다.

이분탐색

 def BS(start, end, n):
    mid = (start+end)//2

    # 찾는 수가 없을 경우,
    if start > end: return 0

    # 찾는 수가 중간지점의 수보다 큰 경우,
    if n > N_num_sort[mid]:
        return BS(mid+1, end, n) # 오른쪽 부분 탐색
    
    # 찾는 수가 중간지점의 수보다 작은 경우,
    elif n < N_num_sort[mid]:
        return BS(start, mid-1, n) # 왼쪽 부분 탐색
    else: # 수를 찾은 경우,
        return 1

이분 탐색을 시행하는 함수이다. 시작점이 끝점을 역전하는 경우, 찾는 수가 없다는 의미이므로 0을 반환해준다.

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
N_num = list(map(int, input().split()))
M = int(input())
M_num = list(map(int, input().split()))

N_num_sort = sorted(N_num)

def BS(start, end, n):
    mid = (start+end)//2

    if start > end: return 0
    if n > N_num_sort[mid]:
        return BS(mid+1, end, n)
    elif n < N_num_sort[mid]:
        return BS(start, mid-1, n)
    else:
        return 1
    
for i in M_num:
    sys.stdout.write("%d "%BS(0, N-1, i))

댓글남기기

참고