문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

www.acmicpc.net/problem/10815

  • 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 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을 공백으로 구분해 출력한다.

최종 코드

이번 문제에서는 해결 방법으로 총 4가지를 발견했다. 순서대로

  1. 이분탐색
  2. 리스트
  3. 집합
  4. 딕셔너리

가 있다.

1. 이분탐색

num in arr를 사용하면 시간복잡도가 O(N)으로 당연히 시간 초과이다. 이분탐색 문제이기 때문에 search라는 함수에서 이분탐색을 통해 숫자를 찾는 방법으로 해결했다.

import sys

def search(n):
    left = 0
    right = len(deck) - 1
    while left <= right:
        mid = (left + right) // 2
        if deck[mid] == n:
            return True
        elif deck[mid] > n:
            right = mid - 1
        else:
            left = mid + 1
    return False

n = int(sys.stdin.readline())
deck = list(map(int, sys.stdin.readline().split()))
deck = sorted(deck)
m = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

for num in arr:
    if search(num):
        print(1, end=" ")
    else:
        print(0, end=" ")

2. 리스트

아니 근데 메모리만 넉넉하면 제일 빠른 건 리스트 아닌가? 그래서 리스트로도 풀어보았다. 메모리가 아슬아슬하긴 했지만 어쨌건 이분탐색보다 3배 정도 빠른 시간으로 통과했다. 메모리만 넉넉하면 이 방법도 나쁘지 않지 않을까?

import sys
n = int(sys.stdin.readline())
deck = list(map(int, sys.stdin.readline().split()))
check = [0]*20000001
for i in deck:
    check[i+10000000] = 1
m = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

for num in arr:
    if check[num+10000000]:
        print(1, end=" ")
    else:
        print(0, end=" ")

Enhanced

3. 딕셔너리

세 번째 방법은 딕셔너리다. 딕셔너리나 밑에 나올 집합을 사용하면 리스트보다 속도가 훨씬 빠르다는 건 이번에 처음 알게 되었다! 딕셔너리에 간단하게 저장하는 방법도 알게 되었다. 잘 기억해뒀다가 써먹어야지.

import sys

n = int(sys.stdin.readline())
deck = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dict = {deck[i]: 0 for i in range(n)}

for num in arr:
    if num in dict.keys():
        print(1, end=" ")
    else:
        print(0, end=" ")

4. 집합

마지막 방법은 집합이다. 중복되는 숫자를 처리할 필요가 없는 경우 집합을 사용할 수 있다. 카드 숫자들을 집합에 저장해서 in을 사용하면 매우 간단하게 해결할 수 있다. 딕셔너리와 마찬가지로 리스트보다 시간도 더 빠르게 나왔다.

import sys

n = int(sys.stdin.readline())
deck = set(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

for num in arr:
    if num in deck:
        print(1, end=" ")
    else:
        print(0, end=" ")

백준 10816번: 숫자 카드 2

10816번 문제 -> www.acmicpc.net/problem/10816

10815번 숫자 카드 문제와 비슷한데, 숫자의 존재 여부가 아니라 숫자의 개수를 구해야 하는 문제이다.

비슷한 문제인데 이진 탐색을 하면 시간이 초과된다. 숫자가 중복되므로 집합도 사용할 수 없다. 따라서 리스트나 딕셔너리를 사용해야 한다.

또 다른 방법으로는 이진탐색을 위한 bisect 라이브러리를 사용할 수 있다. 라이브러리도 있다는 걸 적어두고 싶었다. 자세한 내용은 여기를 참고하자.

참고 사이트