# 집합 생성 방법
empty = set()                         # 빈 집합
numbers = {1, 2, 3}                   # 중괄호로 생성
string_set = set("Hello")             # 문자열로 생성 -> {'H', 'e', 'l', 'o'}
list_set = set([1, 2, 2, 3, 3])      # 리스트로 생성 -> {1, 2, 3}

s1 = {1, 2, 3, 4, 5}
s2 = {4, 5, 6, 7, 8}

# 교집합
print(s1 & s2)                        # {4, 5}
print(s1.intersection(s2))            # {4, 5}

# 합집합
print(s1 | s2)                        # {1, 2, 3, 4, 5, 6, 7, 8}
print(s1.union(s2))                   # {1, 2, 3, 4, 5, 6, 7, 8}

# 차집합
print(s1 - s2)                        # {1, 2, 3}
print(s1.difference(s2))              # {1, 2, 3}

# 대칭차집합 (합집합 - 교집합)
print(s1 ^ s2)                        # {1, 2, 3, 6, 7, 8}
print(s1.symmetric_difference(s2))     # {1, 2, 3, 6, 7, 8}

# 요소 추가
s = {1, 2, 3}
s.add(4)                              # 단일 요소 추가
s.update([5, 6, 7])                   # 여러 요소 추가

# 요소 제거
s.remove(4)                           # 요소 제거 (없으면 KeyError)
s.discard(4)                          # 요소 제거 (없어도 에러 없음)
s.pop()                               # 임의의 요소 제거 후 반환
s.clear()                             # 모든 요소 제거

# 리스트의 중복 제거
numbers = [1, 2, 2, 3, 3, 3]
unique_numbers = list(set(numbers))    # [1, 2, 3]

# 포함 관계 확인
s1 = {1, 2, 3}
s2 = {1, 2}
print(s2.issubset(s1))                # True (부분집합)
print(s1.issuperset(s2))              # True (상위집합)

# 교집합 여부 확인
s3 = {4, 5}
print(s1.isdisjoint(s3))              # True (교집합 없음)

# 기본 형식
squares = {x**2 for x in range(10)}
# {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}

# 조건식 추가
even_squares = {x**2 for x in range(10) if x % 2 == 0}
# {0, 4, 16, 36, 64}

# 다중 조건
mixed = {x for x in range(20) if x % 2 == 0 if x % 3 == 0}
# {0, 6, 12, 18} (2와 3의 공배수)

# if-else 사용
categorized = {x if x % 2 == 0 else -x for x in range(10)}
# {0, -1, 2, -3, 4, -5, 6, -7, 8, -9}

# 문자열 처리
words = ['hello', 'world', 'python', 'programming']
lengths = {len(word) for word in words}
# {5, 6, 11} (중복 제거된 문자열 길이)

# frozenset 생성
immutable = frozenset([1, 2, 3, 4])
print(immutable)  # frozenset({1, 2, 3, 4})

# 집합 연산은 가능
normal_set = {3, 4, 5, 6}
print(immutable & normal_set)  # frozenset({3, 4})
print(immutable | normal_set)  # frozenset({1, 2, 3, 4, 5, 6})

# 변경 시도는 오류 발생
try:
    immutable.add(5)  # 오류: 'frozenset' object has no attribute 'add'
except AttributeError as e:
    print(e)

# 딕셔너리 키나 집합 요소로 사용 가능
set_of_sets = {frozenset({1, 2}), frozenset({3, 4})}
dict_with_sets = {frozenset({1, 2}): 'set1', frozenset({3, 4}): 'set2'}

import timeit
import random

# 데이터 준비
size = 10000
data = list(range(size))
random.shuffle(data)
lookup_value = size - 1

# 리스트 vs 집합 멤버십 검사 성능 비교
list_time = timeit.timeit(
    lambda: lookup_value in data,
    number=1000
)

set_data = set(data)
set_time = timeit.timeit(
    lambda: lookup_value in set_data,
    number=1000
)

print(f"리스트 검색 시간: {list_time:.6f}초")
print(f"집합 검색 시간: {set_time:.6f}초")
print(f"집합이 약 {list_time/set_time:.1f}배 빠름")

# 교집합 계산 성능 (naive vs set)
def naive_intersection(list1, list2):
    return [item for item in list1 if item in list2]

list1 = random.sample(range(size), size//2)
list2 = random.sample(range(size), size//2)

naive_time = timeit.timeit(
    lambda: naive_intersection(list1, list2),
    number=10
)

set_intersection_time = timeit.timeit(
    lambda: set(list1) & set(list2),
    number=10
)

print(f"일반 교집합 구현: {naive_time:.6f}초")
print(f"집합 교집합 연산: {set_intersection_time:.6f}초")
print(f"집합이 약 {naive_time/set_intersection_time:.1f}배 빠름")

# 단어 목록에서 중복과 특정 조건 필터링
words = ['apple', 'banana', 'apple', 'cherry', 'date', 'banana', 'elderberry']

# 중복 제거 및 5글자 초과 단어 필터링
filtered_words = {word for word in words if len(word) > 5}
print(filtered_words)  # {'banana', 'cherry', 'elderberry'}

# 다음과 같이도 활용 가능
unique_sorted_words = sorted(set(words))
print(unique_sorted_words)  # ['apple', 'banana', 'cherry', 'date', 'elderberry']

# 학생들의 수강 과목 분석
student_courses = {
    'Alice': {'math', 'physics', 'chemistry'},
    'Bob': {'math', 'physics', 'biology'},
    'Charlie': {'physics', 'biology', 'computer science'},
    'David': {'math', 'computer science'}
}

# 모든 과목 목록
all_courses = set()
for courses in student_courses.values():
    all_courses.update(courses)
print(f"개설된 모든 과목: {all_courses}")

# 가장 인기 있는 과목 찾기
course_count = {}
for courses in student_courses.values():
    for course in courses:
        course_count[course] = course_count.get(course, 0) + 1

most_popular = max(course_count, key=course_count.get)
print(f"가장 인기 있는 과목: {most_popular} ({course_count[most_popular]}명 수강)")

# 모든 학생이 듣는 공통 과목
common_courses = set.intersection(*student_courses.values())
print(f"모든 학생이 수강하는 과목: {common_courses if common_courses else '없음'}")

# 적어도 한 학생이 듣는 과목
any_courses = set.union(*student_courses.values())
print(f"적어도 한 학생이 수강하는 과목: {any_courses}")

# Two Sum 문제: 배열에서 합이 target인 두 수의 인덱스 찾기
def two_sum(nums, target):
    seen = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            return [num, complement]
        seen.add(num)
    return None

print(two_sum([2, 7, 11, 15], 9))  # [7, 2]

# 문자열에서 중복 없는 가장 긴 부분 문자열 찾기
def longest_substring_without_repeating(s):
    char_set = set()
    max_length = 0
    i = 0
    
    for j in range(len(s)):
        while s[j] in char_set:
            char_set.remove(s[i])
            i += 1
        char_set.add(s[j])
        max_length = max(max_length, j - i + 1)
    
    return max_length

print(longest_substring_without_repeating("abcabcbb"))  # 3 (abc)
print(longest_substring_without_repeating("bbbbb"))     # 1 (b)
print(longest_substring_without_repeating("pwwkew"))    # 3 (wke)

# 그래프에서 연결 요소 찾기
def connected_components(graph):
    visited = set()
    components = []
    
    def dfs(node, component):
        visited.add(node)
        component.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor, component)
    
    for node in graph:
        if node not in visited:
            component = set()
            dfs(node, component)
            components.append(component)
    
    return components

# 인접 리스트로 표현된 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
    'G': ['H'],
    'H': ['G']
}

components = connected_components(graph)
print(f"연결 요소의 개수: {len(components)}")
for i, component in enumerate(components, 1):
    print(f"연결 요소 {i}: {component}")