[백준] 1920 - 수 찾기(실버 4)

https://www.acmicpc.net/problem/1920

1트

Python 의 in 연산 시간 복잡도

list, tuple

• Average: O(n)
• 하나하나 순회한다.set, dictionary
• Average: O(1), Worst: O(n)
• 내부적으로 hash를 통해서 자료들을 저장한다.

#내 풀이

candidate_cases = int(input())
candidates = sorted(list(map(int, input().split())))

target_cases = int(input())
origin_targets = list(map(int, input().split()))

sorted_targets = sorted(origin_targets)
targets_dict = dict()


c_idx = 0
c_len = len(candidates)
t_idx = 0
t_len = len(sorted_targets)

while t_idx < t_len and c_idx < c_len:
    if sorted_targets[t_idx] == candidates[c_idx]:
        targets_dict[sorted_targets[t_idx]] = 1
        t_idx += 1
    elif sorted_targets[t_idx] < candidates[c_idx]:
        targets_dict[sorted_targets[t_idx]] = 0
        t_idx += 1
    else:
        c_idx += 1

while t_idx < t_len:
    targets_dict[sorted_targets[t_idx]] = 0
    t_idx += 1

for key in origin_targets:
    print(targets_dict[key])

# 감동받은 코드
input()
dic ={}
for k in input().split(): dic[k]=1
input()
for k in input().split(): print(dic.get(k,0))

# 감동받은 코드2
I=input;I();a=set(I().split());I()
for b in I().split():print(int(b in a))