[백준] 1822. 차집합

백준 1822. 차집합

1822번: 차집합

 

✓ 난이도 : 실버 4

✓ 문제 풀이 : 이분탐색, set 함수 사용 (차집합)

 

< 이분탐색 사용 > 

import math
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = []

b.sort()
for x in a:
    tmp = x
    s, e = 0, m-1
    while s <= e:
        mid = (s+e)//2

        if b[mid] == x:
            tmp = 0
            break

        elif b[mid] < x:
            s = mid+1

        else:
            e = mid-1

    if tmp != 0:
        res.append(tmp)
        
print(len(res))
if len(res) > 0:
    print(*sorted(res))

 

< set 사용 >

import sys
input = sys.stdin.readline

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

res = list(set(a)-set(b))
res.sort()

print(len(res))
if len(res) != 0:
    print(' '.join(map(str, res)))

 

---

내장함수인 set을 사용하는 것이 훨씬! 시간이 빨랐다. 아무래도 set의 특성때문인 것 같다. 그치만 공간 메모리는 이분탐색이 더 작은 것을 알 수 있었다. set 함수도 좀 더 공부해야겠다.