[알고리즘] 백준 1269번 대칭 차집합 python - 해시 맵, 집합

Created

2022/07/19

Tags

Algorithm

Python

HashMap

2022-07-19 @이영훈

1269번: 대칭 차집합

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

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

접근 방법

문제에서 각 집합 원소의 최대 개수는 200,000개 이기 때문에 이중 반복문을 사용하여서 O(n^2)로 문제를 해결할 경우 200,000 * 200,000 > 1억 이기 때문에 시간초과가 됩니다.

해시맵으로 접근하였습니다. 해시 맵으로 접근할 경우 최대 200,000 + 200,000 = 400,000번만 접근하면 되기 때문에 시간 초과가 나지 않고 문제를 해결할 수 있습니다.

해시맵에 두 집합의 원소의 개수를 셉니다. 그리고 해시맵에서 개수가 1개인 원소의 개수를 반환합니다

파이썬 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

# 해시맵에 두 개의 집합 원소의 개수를 셉니다
hash_map = dict()
for _ in range(2):
    for num in input().split():
        if hash_map.get(num, 0) == 0:
            hash_map[num] = 1
        else:
            hash_map[num] += 1

# 해시맵에서 개수가 1개인 원소의 개수를 확인합니다
answer = 0
for value in hash_map.values():
    if value == 1:
        answer += 1

print(answer)
Python
복사