파이썬) 차집합 - BOJ

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

1822번: 차집합

 

이문제는 이분탐색으로 분류된 문제였다.

그래서 이분탐색으로 풀어봤다.

 

na, nb = map(int, input().split())


a = list(map(int, input().split()))
b = list(map(int, input().split()))


b.sort()
answer = 0

for target in a:
    temp = False

    start = 0
    end = len(b)-1

    while start <= end:
        mid = (start + end) // 2

        if target == b[mid]:
            temp = True
            break
        elif target < b[mid]:
            end -= 1
        else:
            start += 1

    if not temp:
        answer += 1
print(answer)

우선 a에 속하면서 b에 속하지 않은 숫자를 출력하지 않은 것도 문제지만 애초에 시간초과가 발생했다.

때문에 어쩔 수 없이 딕셔너리로 풀어봤다.

 

na, nb = map(int, input().split())


a = list(map(int, input().split()))
b = list(map(int, input().split()))

dic = {}

for i in b:
    dic[i] = 1

answer = 0
arr = []

for i in a:
    if i not in dic:
        answer += 1
        arr.append(i)
print(answer)
arr.sort()
for i in arr:
    print(i, end=' ')

 

지금 이 글을 작성하면서 다시 봤는데 이 문제의 알고리즘은 

자료구조, 정렬, 해시맵, 트리맵으로 어디에도 이분탐색은 없다... 대체 뭘 본거지...