[Algorithm] 백준 10815번 숫자 카드 (Python)

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 0 1 1 0 0 1

풀이

설명

• 순차탐색을 하면 시간초과가 발생하므로 이진탐색을 한다.

코드

• 실패 - 시간초과

import sys
input = sys.stdin.readline

N = int(input())
card = list(map(int, input().split()))
M = int(input())
check_card = list(map(int, input().split()))

for i in check_card:
    if i in card:
        print(1, end=" ")
    else:
        print(0, end=" ")

• 성공 - 이진탐색 사용

이진 탐색 알고리즘
: 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
- 탐색 범위를 절반씩 좁히면서 데이터를 탐색한다. -> 시간 복잡도: O(log N)
- 정렬된 데이터에서 원하는 데이터를 빠르게 찾을 수 있다.

bisect 라이브러리
: 이진 탐색을 쉽게 구현할 수 있도록 제공된 라이브러리
- 정렬된 배열에서 특정한 원소를 찾아야 할 때 효과적이다.
- bisect_left(list, x)
: 정렬된 순서를 유지하면서 list에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
- bisect_right(list, x)
: 정렬된 순서를 유지하면서 list에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
- 위 두 메서드를 이용하여 값이 특정 범위에 속하는 원소의 개소를 구할 수 있다. (right - left)

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

N = int(input())
card = list(map(int, input().split()))
M = int(input())
check_card = list(map(int, input().split()))

card.sort()

for i in check_card:
    left = bisect_left(card, i)
    right = bisect_right(card, i)
    print(right - left, end=" ")