[Python] 백준 풀기 1269 - 대칭 차집합

파이썬 백준 1269번

실버 4

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

1269번: 대칭 차집합

 

 

 

 

 

문제 보기

분류: 자료 구조, 해시를 사용한 집학과 맵, 트리를 사용한 집학과 맵

 

 

 

 

 

문제 풀기

각 집합의 원소의 개수가 200,000 개여서 시간 초과 안걸릴거라 생각했다가 제출하고 보니 x in List 연산 이 O(n) 의 시간 복잡도를 갖는다는 것을 알았다.

 

 

이번 기회를 통해 파이썬의 집합 기호에 대해 알게 되었다.

 

교집합

    set_a & set_b

 

합집합

    set_a | set_b

 

차집합

    set_a - set_b

 

대칭 차집합

    set_a ^ set_b

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnNumberOfElements(b_cnt):
    result_ls = a_ls ^ b_ls         ## 대칭 차집합.
    print(len(result_ls))


if __name__ == "__main__":
    a_cnt, b_cnt = map(int, inputdata().split())
    a_ls = set(map(int, inputdata().split()))
    b_ls = set(map(int, inputdata().split()))
    
    fnNumberOfElements(b_cnt)

 

 

 

 

추가 하기

처음에 제출하였던 답은 나오는데 시간 초과한 코드

import sys
inputdata = sys.stdin.readline


def fnNumberOfElements(b_cnt):
    plus_cnt = 0
    minus_cnt = 0
    for a in a_ls:
        if a not in b_ls:
            plus_cnt += 1
        elif a in b_ls:
            minus_cnt += 1
    
    total_count = plus_cnt + (b_cnt - minus_cnt)
    print(total_count)


if __name__ == "__main__":
    a_cnt, b_cnt = map(int, inputdata().split())
    a_ls = list(map(int, inputdata().split()))
    b_ls = list(map(int, inputdata().split()))
    
    fnNumberOfElements(b_cnt)

 

 

 

메모리 초과한 코드

import sys
inputdata = sys.stdin.readline


def fnNumberOfElements(b_cnt):
    for a in a_ls:
        num_ls[a] = 1
    for b in b_ls:
        if num_ls[b] == 1:
            num_ls[b] = 0
        else:
            num_ls[b] = 1
    
    print(sum(num_ls))


if __name__ == "__main__":
    a_cnt, b_cnt = map(int, inputdata().split())
    a_ls = list(map(int, inputdata().split()))
    b_ls = list(map(int, inputdata().split()))
    
    num_ls = [0] * 100_000_002
    fnNumberOfElements(b_cnt)

 

 

 

파이썬 집합 기호

https://xcevor.tistory.com/193

[Python] 교집합, 합집합, 차집합, 대칭 차집합