Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 라이브러리 집합 클래스를 사용하지 않고 집합 데이터 구조를 정의하는 프로그램

<시간/>

다음 방법을 사용하여 집합 데이터 구조를 구현한다고 가정합니다. -

  • 집합의 새 인스턴스를 생성하는 생성자
  • 집합에 정수 val을 삽입하는 add(val)
  • exists(val) val이 집합에 있는지 여부를 확인합니다.
  • remove(val)를 사용하여 집합에서 val을 제거합니다.

따라서 집합 s를 구성하면 s.add(10), s.add(20), s.add(10), s.exists(10), s.remove(10), s.exists( 10), s.exists(20), 출력은

  • s.add(10)의 경우 10을 삽입합니다.
  • s.add(20)의 경우 20을 삽입합니다.
  • 10은 이미 s에 있으므로 아무 일도 일어나지 않습니다.
  • s.exists(10)은 10이 있으면 true를 반환합니다.
  • s.remove(10)로 10개 삭제
  • s.exists(10)은 10이 제거되고 하나의 요소가 한 번만 존재할 수 있기 때문에 false를 반환합니다.
  • s.exists(20)는 20이 존재하므로 true를 반환합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 생성자를 정의합니다.
  • buckets :=빈 지도이며 여기에는 데이터 목록이 저장됩니다.
  • add() 함수를 정의합니다. 시간이 걸립니다
  • 존재하는(val)이 거짓이면
    • 버킷 끝에 val 삽입[val]
  • exist() 함수를 정의합니다. 시간이 걸립니다
  • val이 버킷[val]에 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
  • remove() 함수를 정의합니다. 시간이 걸립니다
  • 버킷 삭제[val]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import defaultdict
class MySet:
   def __init__(self):
      self.buckets = defaultdict(list)

   def add(self, val):
      if not self.exists(val):
         self.buckets[val].append(val)

   def exists(self, val):
      return val in self.buckets[val]

   def remove(self, val):
      del self.buckets[val]

s = MySet()
s.add(10)
s.add(20)
s.add(10)
print(s.exists(10))
s.remove(10)
print(s.exists(10))
print(s.exists(20))

입력

s = MySet()
s.add(10)
s.add(20)
s.add(10)
s.exists(10)
s.remove(10)
s.exists(10)
s.exists(20)

출력

True
False
True