[ 알고리즘 ] 백준 10815번: 숫자 카드

이주 weekwith.me·2022년 7월 31일

목록 보기

44/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 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을 공백으로 구분해 출력한다.

풀이

접근법

가지고 있는 숫자 카드는 오름차순으로 정렬한 뒤 이후 비교를 위해 주어지는 카드를 반복문을 돌면서 이진 탐색을 수행하면 된다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


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

for target in list(map(int, input().split())):
    flag: int = 0
    start, end = 0, N-1
    while start <= end:
        middle = (start + end) // 2
        card = cards[middle]

        if target == card:
            flag = 1
            break

        elif target < card:
            end = middle - 1

        else:
            start = middle + 1

    print(flag, end=" ")

다른 풀이

아래와 같이 bisect 내장 모듈을 활용해서 문제를 풀 수도 있다.

동일한 요소가 배열에 존재하지 않을 경우 처음으로 특정 인덱스에 요소를 삽입하기 때문에 좌측과 우측의 인덱스가 동일할 수밖에 없다.

따라서 좌측 인덱스와 우측 인덱스를 뺐을 때 만약 0이라면 해당 요소는 배열에 존재하지 않았던 요소임을 의미한다.

import sys
import bisect


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

for target in list(map(int, input().split())):
    left_value = bisect.bisect_left(a=cards, x=target)
    right_value = bisect.bisect_right(a=cards, x=target)

    print(0, end=" ") if not(right_value - left_value) else print(1, end=" ")