[자료구조] 집합 (Set)

집합: 항목들이 나열되어 있는 중복과 순서가 없는 자료구조.

리스트와 유사한 구조이나 집합에는 중복되는 요소가 없으며 순서가 존재하지 않는다는 차이가 있다.

 

집합의 기능

• size(): 집합의 원소 개수를 반환한다.
• contains(e): 집합이 e라는 원소를 포함하는지 검사한다.
• insert(e): 원소 e를 새로 삽입하나 이미 e가 있다면 삽입하지 않음.
• delete(e): 원소 e를 집합에서 삭제하고 반환한다.
• equals(setB): setB와 같은 집합인지 검사한다.
• union(setB): setB와의 합집합을 만들어 반환한다.
• intersect(setB): setB와의 교집합을 만들어 반환한다.
• difference(setB): setB와의 차집합을 만들어 반환한다.
• display(): 집합을 출력한다.

---

집합의 구현

class Set:
    def __init__(self):
        self.items = []

    def size(self):
        return len(self.items)

    def display(self, msg):
        print(msg, self.items)

    def contains(self, e):
        return e in self.items

    def contains2(self, e):
        for i in range(len(self.items)):
            if items[i] == e:
                return True
            else:
                return False

    
    def insert(self, item):
        if item not in self.items:
            self.items.append(item)

    def delete(self, item):
        if item in self.items:
            self.items.remove(item)

    def equals(self, setB):
        result = True
        if self.size() == setB.size():
            for i in self.items:
                if i not in setB.items:
                    result = False
        else:
            result = False
        print(result)

    def union(self, setB):
        setC = Set()
        setC.items = list(self.items) # list()함수 없으면 setC와 self가 같은 객체 주소 가리키니까 두 개 같아짐... 꼭 list()를 써줘야 함.

        for i in setB.items:
            if i not in self.items:
                setC.items.append(i)
        return setC

    def intersect(self, setB):
        setC = Set()

        for i in setB.items:
            if i in self.items:
                setC.items.append(i)
        return setC

    def difference(self, setB):
        setC = Set()

        for i in self.items:
            if i not in setB.items:
                setC.items.append(i)
        return setC

 

시간복잡도
insert(), delete(): O(n)

union(), intersect(), difference(): O(n^2)

 

작성일자: 2023-02-27