[1822] 차집합

문제

출처
몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력 
4 3 (집합A의 수 집합B의 수)
2 5 11 7 (집합 A의 원소)
9 7 4 (집합 B의 원소)

출력 
3 (집합 A-B 원소의 개수)
2 5 11 (집합 A-B)

문제 정리

• A에 있지만 B에 없는 원소를 찾는 문제이다.
• 파이썬에서는 set이 이미 잘 구현되어 있어 따로 자료구조를 만들 필요가 없다.
• 해시테이블을 사용하여 매우 빠른 자료구조이기에 정렬만 해주면 된다.
• 또는 이분 탐색으로 접근하는 방법도 있다.

문제 풀이

1. 첫번째 풀이 : set을 이용한 풀이

# A집합에는 속하지만 B집합에는 속하지 않는 원소를 구하여라
a, b = map(int,input().split())
a_nums = set(map(int, input().split()))
b_nums = set(map(int, input().split()))
complement = a_nums-b_nums
complement = sorted(complement)
if len(complement)>0:
    print(len(complement))
    for c in complement:
        print(c,end=' ')
else :
    print(0)

2. 두번째 풀이 : 반복문을 통한 이분탐색

a, b = map(int, input().split())
a_nums = set(map(int, input().split()))
b_nums = set(map(int, input().split()))

a_nums = sorted(a_nums) # 정렬을 안해도 되지만 그렇게 되면 나중에 결과 리스트를 정렬해줘야함.
b_nums = sorted(b_nums)

not_in_b_but_a = []

for a_num in a_nums:
    start = 0
    end = len(b_nums) - 1
    found = False
    while start <= end:
        mid = (start + end) // 2
        if b_nums[mid] == a_num:
            found = True
            break
        elif b_nums[mid] < a_num:
            start = mid + 1
        else:
            end = mid - 1
    if not found:
        not_in_b_but_a.append(a_num)

length = len(not_in_b_but_a)
print(length)
if length != 0:
    for num in not_in_b_but_a:
        print(num, end=' ')

3. 세번째 풀이 : 파이썬의 bisect 모듈을 이용한 이분 탐색

from bisect import bisect_left, bisect_right
a, b = map(int, input().split())
a_nums = set(map(int, input().split()))
b_nums = set(map(int, input().split()))
b_nums = sorted(b_nums)
not_in_b_but_a = []
for a in a_nums:
    not_in_b_left = bisect_left(b_nums, a)
    not_in_b_right = bisect_right(b_nums, a)
    if not_in_b_right-not_in_b_left == 0:
        not_in_b_but_a.append(a)
not_in_b_but_a.sort() # 이번엔 A집합을 정렬하지 않고 시작해 결과에서 정렬진행
length = len(not_in_b_but_a)
print(length)
if length != 0:
    for num in not_in_b_but_a:
        print(num, end=' ')