[Python] BOJ 10815번: 숫자 카드

10815번: 숫자 카드

3차 시도

1차 시도로 복귀하여 살펴보니, in 연산의 시간 복잡도가 연산을 수행할 자료구조에 따라 달라질 수 있겠다고 생각했다.

1차 시도에 사용한 코드에서 사용할 자료구조를 set으로 변경하여 성공했다.

자료구조	평균	최악
list, tuple	O(n)	O(n)
set, dict	O(1)	O(n)

출처: TimeComplexity - Python Wiki

import sys

own, test = map(lambda x: map(int, x.split()), sys.stdin.readlines()[1::2])
own = set(own)
test = list(test)
print(*map(lambda x:1 if x in own else 0, test))

---

1차 시도

import sys

own, test = map(lambda x: tuple(map(int, x.split())), sys.stdin.readlines()[1::2])
print(*map(lambda x:1 if x in own  else 0, test))

Python 키워드 in을 활용하여 각각의 tuple에 대한 검색 연산을 수행

 

2차 시도

import sys

own, test = map(lambda x: list(map(int, x.split())), sys.stdin.readlines()[1::2])


# 목표: 주어진 배열 안에 전달한 값이 몇 번 인덱스에 존재하는지 return
def search(e, es, i_from, i_to):
    l = len(es) - 1
    while i_from <= i_to:
        idx = (i_from + i_to) // 2
        if e == es[idx]:
            return idx
        elif e < es[idx]:
            i_to = idx - 1
        elif e > es[idx]:
            i_from = idx + 1
        if l < i_from or i_to < 0: break
    return -1

table = {}
idx = 0
for t in sorted(test):
    if t in table.keys(): continue
    tmp = search(t, sorted(own), idx, len(own) - 1)
    table[t]=tmp
    if tmp != -1: idx = tmp

print(*list(map(lambda x: 1 if table[x] >=0 else 0, test)))

두 정렬된 리스트의 이분 탐색으로 시도했으나, 시간 초과로 실패