[Python] BOJ 1269 대칭차집합

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

요구사항

• 시간 제한: 2초 
• 메모리 제한: 256MB

결론: 각 집합의 원소의 개수 200,000. 약 2억까지 괜찮으니 O(N**2)아래로 가자. 

 

설계 1 (최종 답안은 설계 3을 참고해주세요.)

• a = [1, 2, 4]
• b = [2, 3, 4, 5, 6]
• a를 순회하며 b가 있는 지 체크 한다. count_a += 1
• b를 순회하며 a가 있는 지 체크한다. count_b += 1
• print(count_a + count_b) 

import sys
input = lambda: sys.stdin.readline().rstrip()

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

count_a = 0
count_b = 0

for i in b:
    if i not in a:
        count_a += 1

for i in a:
    if i not in b:
        count_b += 1

print(count_a + count_b)

• 위 방법 시간 초과가 난다. 
• 이 때는 2번의 for문으로 시간초과가 난다고 생각하였음. 
• 하나의 for문으로 어떻게 구현하지 생각함.

설계 2 

• a = [1, 2, 4]
• b = [2, 3, 4, 5, 6]
• 둘의 공통은 2와 4 총 2개이다. 
• len(a) - 2 + len(b) - 2 = 4이다. 
• 즉, 한 번의 for문으로도 구현 가능

import sys
input = lambda: sys.stdin.readline().rstrip()

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

count = 0

for i in b:
    if i in a:
        count += 1

print(len(a) + len(b) - (count * 2))

• 여전히 시간초과 발생. 
• 문제는 for문이 2개냐 1개냐의 문제가 아니였음...
• for i in b 에서 O(M) 이 걸린다고 치자. 
• if i in a -> 비교만 해서 O(1)이라고 생각했는 데, 반만 맞다. 비교 자체는 O(1)이겠지만, a를 순회할 거니깐. O(N)
• 따라서 O(M * N) 의 시간복잡도를 갖는다. 즉, 요구사항인 2초를 훌쩍 넘어버리는 것. 

설계 3

• a와 b 를 list가 아닌 set 자료구조로 받는다.
• 그 이유는 수학에서 집합은 서로 다른 원소들의 모임이기 때문에 집합을 허용하지 않는다. 
• 파이썬의 set은 해시 테이블 기반으로 구현. 탐색, 추가, 삭제 연산이 평균적으로 O(1)
• set 자료구조는 교집합 연산을 제공한다. O(min(N, M) 
  • 작은 쪽을 기준으로 각 원소를 큰 쪽에서 찾기 때문
  • a = {1, 2, 4}
  • b = {2, 3, 4, 5, 6}
  • a & b # {2, 4}
• 참고) 한 집합의 크기가 매우 크고 다른 집합의 크기가 매우 작다면, 작은 집합의 우너소를 하나씩 큰 집합에서 검색하는 것이 더 효율적일 수 있다. 

import sys
input = lambda: sys.stdin.readline().rstrip()

a_size, b_size = map(int, input().split())
a = set(map(int, input().split()))
b = set(map(int, input().split()))

print((len(a) + len(b)) - (len(a & b) * 2) )

 

회고

set 자료구조에 대해 리마인드 할 수 있어서 좋았다. 특히, set 자료구조에서 & method 는 충격적이다. 

헷갈리는 용어

메서드 vs 라이브러리 vs 프레임워크

 

- 메서드란 객체에 속한 함수. 특정 객체(클래스의 인스턴스)가 사용하는 함수. 예를 들어, list.append(), set.intersection()

 

- 라이브러리란: 여러 개의 메서드, 클래스 등을 모아둔 코드 집합 import math,,

 

- 프레임워크: 코드의 뼈대를 제공하고, 거기에 코드를 추가하는 구조