[학습동아리] 1일차 07/05

활동일시 : 1일차 2023-07-05 21:30-23:30

목표 : 백준 1269번 [대칭 차집합] 문제 풀이(https://www.acmicpc.net/problem/1269)

알고리즘 분류

• 자료 구조
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

풀이1

len1, len2 = map(int, input().split())

list1 = list(map(int, input().split()))
list2 = list(map(int, input().split()))

# 첫번째는 A를 기준으로 B에 없는 원소의 개수를 알아낸다.
count1 = len(list1)
for i in range(0, len(list1)):
    for j in range(0, len(list2)):
        if list1[i] == list2[j]:
            count1 -= 1
            continue
# 두번째는 B를 기준으로 A에 없는 원소의 개수를 알아낸다.
count2 = len(list2)
for i in range(0, len(list2)):
    for j in range(0, len(list1)):
        if list2[i] == list1[j]:
            count2 -= 1
            continue

result = count1+count2
print(result)

이중 반복문을 두번 사용하여 각 원소를 비교하였으나 시간초과로 실패

풀이2

len1, len2 = map(int, input().split())

list1 = list(map(int, input().split()))
list2 = list(map(int, input().split()))

# 첫번째는 A를 기준으로 B에 없는 원소의 개수를 알아낸다.
count1 = len(list1)
for i in range(0, len(list2)):
    if list2[i] in list1:
        count1 -= 1
# 두번째는 B를 기준으로 A에 없는 원소의 개수를 알아낸다.
count2 = len(list2)
for i in range(0, len(list1)):
    if list1[i] in list2:
        count2 -= 1

result = count1+count2
print(result)

if in으로 비교하였으나 시간초과로 실패

풀이3

len1, len2 = map(int, input().split())

list1 = list(map(int, input().split()))
list2 = list(map(int, input().split()))

differ1 = set(list1) - set(list2)
differ2 = set(list2) - set(list1)

result = len(differ1) + len(differ2)
print(result)

파이썬 집합 연산자를 통해 구현하였다.
집합 A와 B에 대해 각각 A에 대한 B의 차집합인 A-B, B에 대한 A의 차집합인 B-A의 원소의 개수를 구한 후 더해주었다.

느낀점

오늘은 1학년 때 잠깐 배웠던 파이썬과 저번 학기에 배웠던 자료구조의 복습을 위한 집합 문제를 풀어보았다.
파이썬에서는 내장함수 set()을 통해 간단하게 집합을 구현하고 연산할 수 있었다.
쉬운 문제였으나 수업의 과제와는 달리 시간제한이 있어서 시간을 넘기지 않고 구현하는 게 힘들었고, 코드를 변경하여도 시간이 얼마나 늘어나거나 얼마나 단축되는지 잘 알지 못해서 더욱 헷갈렸던 것 같다.
시간 복잡도에 대해서도 조금 더 공부할 필요가 있을 것 같다.