set() & dict() - 집합과 맵

🏄🏽‍♂️ 대표 자료구조 '집합'과 '맵'이 있다. 두 개의 자료구조는 매우 효율적인 자료구조로 특별히 python에서 어떻게 코드로 구현하고, 관련 여러 연산 기능 및 time complexity까지 자세히 알아보자!

 

🏄🏽‍♂️ 시간복잡도 계산 상 효율적인 코드를 작성하기 위해 집합과 맵이라는 자료구조를 활용하는 경우가 많다(특히 어려운 PS 문제!) 각 자료구조의 특징을 정확히 알아보자

Sets

overview

"unordered collection of data types that is iterable, mutable and has no duplicate elements. The order of elements in a set is undefined though it may consist of various elements. The major advantage of using a set, as opposed to a list, is that it has a highly optimized method for checking whether a specific element is contained in the set. Basic uses include membership testing and eliminating duplicate entries. Set objects also support mathematical operations like union, intersection, difference, and symmetric difference."

 

→ 중복을 허용하지 않는다는 점이 주목할 만한 특징!

→ 또한 unordered collection으로 집합 내에 원소의 순서가 정해져 있지 않으므로 slicing이나 indexing이 불가능하다.

methods & operations

① set()

: set() 함수로 집합을 만들수 있다. 이 때, 이미 만든 문자열, list, dictionary를 set() 집합으로 만들 수 있다. (dictionary를 set으로 바꾸는 순간 dictionary의 key가 중복 없이 집합으로 저장됨. dictionary의 key 자체가 중복을 허용하지 않으므로 dictionary의 key 모음이라고 할 수 있음)

A = 'hello' #{'l', 'e', 'o', 'h'}
B = [0, 1, 2, 3, 3, 4, 5, 6] #{0, 1, 2, 3, 4, 5, 6}
C = ('a', 'a', 'b', 'c', 'd', 'e', 'f', 'g') #{'d', 'a', 'f', 'c', 'b', 'g', 'e'}
D = {'a': 1, 'b': 2, 'c': 3} #{'a', 'c', 'b'}

print(set(A))
print(set(B))
print(set(C))
print(set(D))

 

② add()

: existing set에 원소를 추가하는 함수를 add()라고 한다. 오로지 단 1개의 원소만 add() 함수로 기존 집합에 추가할 수 있으며, list는 add 불가능. tuple은 가능하다.

 

③ update()

: add()와 다르게 update()는 두 개 이상의 원소를 추가할 수 있다. list, string, tuple, 그리고 다른 set까지 모두 가능하다. 당연히 중복 원소는 허용하지 않게 set를 업데이트한다.

a = set()

a.add(1)
print(a) #{1}

a.update([2,3])
print(a) #{1,2,3}

a.update({4,5,5,6,6})
print(a) #{1,2,3,4,5,6}

 

④ in

: 앞서 얘기했지만, set은 unordered collection이므로 index가 존재하지 않아 indexing / slicing으로 set 안의 원소를 불러올 수 없다. for loop을 작성하거나 in을 이용해 집합에 존재하는 지의 여부를 알 수 있다.

a = {1,2,3,4,5,6}

for x in a:
    print(x,end=' ')

print(3 in a)
#1 2 3 4 5 6 True

 

⑤ remove() / discard() / pop() / clear()

: remove()와 discard()는 특정 원소를 집합에서 제거하는 함수이다. remove()는 제거하려는 원소가 없으면 KeyError를 발생시키지만, discard()는 제거하려는 원소가 없으면 그냥 pass한다. pop() 함수는 집합의 원소 중 랜덤하게 한 개의 원소를 선택해 삭제하고, clear()는 set 원소 전체를 삭제하는 함수이다.

a = {1,2,3,4,5,6}

a.remove(4)
print(a) #{1,2,3,5,6}

a.discard(7)
a.discard(2)
print(a) #{1,3,5,6}

a.pop()
print(a) #{3,5,6}

a.clear()
print(a) #set()

 

⑥ union(|) / intersection(&) / difference(-) / symmetric difference(^)

: 왼쪽부터 차례대로 합집합 / 교집합 / 차집합 / 대칭 차집합(양쪽 차집합 모두)

a = {1,2,3,4,5,6}
b = {1,2,3,5,7,8}

print(a.union(b)) #{1, 2, 3, 4, 5, 6, 7, 8}
print(a|b) #{1, 2, 3, 4, 5, 6, 7, 8}

print(a.intersection(b)) #{1, 2, 3, 5}
print(a&b) #{1, 2, 3, 5}

print(a.difference(b)) #{4,6}
print(a-b) #{4,6}

print(a.symmetric_difference(b)) #{4, 6, 7, 8}
print(a^b) #{4, 6, 7, 8}

advantages & disadvantages

→ Advantages:

★ Unique Elements: Sets can only contain unique elements, so they can be useful for removing duplicates from a collection of data.

★ Fast Membership Testing: Sets are optimized for fast membership testing, so they can be useful for determining whether a value is in a collection or not.

★ Mathematical Set Oerations: Sets support mathematical set operations like union, intersection, and difference, which can be useful for working with sets of data.

★ Mutable: Sets are mutable, which means that you can add or remove elements from a set after it has been created.

 

→ Disadvantages:

★ Unordered: Sets are unordered, which means that you cannot rely on the order of the data in the set. This can make it difficult to access or process data in a specific order.

★ Limited Functionality: Sets have limited functionality compared to lists, as they do not support methods like append() or pop(). This can make it more difficult to modify or manipulate data stored in a set.

★ Memory Usage: Sets can consume more memory than lists, especially for small datasets. This is because each element in a set requires additional memory to store a hash value.

★ Less Commonly Used: Sets are less commonly used than lists and dictionaries in Python, which means that there may be fewer resources or libraries available for working with them. This can make it more difficult to find solutions to problems or to get help with debugging.

time complexity

operation	time complexity	code
creating a new set	O(1)	a = set()
creating a set from an iterable	O(N)	a = set([1,2,3,4,...N])
adding an element	O(1)	a.add(1)
removing an element	O(1)	a.remove(1) / a.discard(2) / a.pop()
checking for element membership	O(1)	1 in a
clearing the set	O(1)	a.clear()
union(|)	O(len(s) + len(t))	s and t are the two sets being united
intersection(&)	O(min(len(s), len(t))
difference(-)	O(len(s))	s is the set from which elements are being removed
symmetric difference(^)	O(len(s) + len(t))	s and t are the two sets being united

Dictionaries

overview

"dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can’t use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend(). It is best to think of a dictionary as a set of key: value pairs, with the requirement that the keys are unique (within one dictionary). A pair of braces creates an empty dictionary: {}. Placing a comma-separated list of key:value pairs within the braces adds initial key:value pairs to the dictionary; this is also the way dictionaries are written on output. The main operations on a dictionary are storing a value with some key and extracting the value given the key. It is also possible to delete a key:value pair with del. If you store using a key that is already in use, the old value associated with that key is forgotten(change a value). It is an error to extract a value using a non-existent key.

techniques

① making a dictionary / change, delete, access

#1
tel = {'jack': 4098, 'sape': 4139}

#2
dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])

#3
dict(sape=4139, guido=4127, jack=4098)

#4
dict({1: 'Geeks', 2: 'For', 3: 'Geeks'})

#using tel dictionary
tel['guido'] = 4127 #add
tel['sape'] = 4111 #change
print(tel) #{'jack': 4098, 'sape': 4111, 'guido': 4127}
print(tel['jack']) #4098 - accessing

print('guido' in tel) # True - check key in a dictionary

del tel['sape'] 
print(tel) #{'jack': 4098, 'guido': 4127}

tel.pop('guido')
print(tel) #{'jack': 4098}

tel.popitem()
print(tel) #{} removes the last inserted key-value pair

 

② looping, sorted, 그 외 여러 dictionary 함수들

→ dictionary를 for loop으로 돌기 위해 dictionary_name.items()를 돌린다.

for k, v in tel.items():
    print(k,v)

'''
jack 4098
sape 4111
guido 4127
'''

 

→ keys()와 values()로 각각 key와 value list 출력

print(tel.keys()) #dict_keys(['jack', 'sape', 'guido'])
print(tel.values()) #dict_values([4098, 4111, 4127])

 

→ sort (dictionary sorting 꼭 기억하기!)

my_dict = {'banana': 3, 'apple': 1, 'orange': 2}

print(sorted(my_dict.items(), key=lambda item: item[1])) #Sorted based on values
#[('apple', 1), ('orange', 2), ('banana', 3)]

print(sorted(my_dict.items(), key=lambda item: item[0])) #Sorted based on keys
#[('apple', 1), ('banana', 3), ('orange', 2)]

print(sorted(my_dict.items(), key=lambda item: item[1], reverse = True)) #Sorted based on values in reverse order
#[('banana', 3), ('orange', 2), ('apple', 1)]

#or
print(sorted(my_dict.items(), key=lambda item: -item[1])) #only applied in numbers
#[('banana', 3), ('orange', 2), ('apple', 1)]

my_dict = {'banana': 1, 'apple': 1, 'orange': 2}
print(sorted(my_dict.items(), key=lambda item: (item[1], item[0]))) #sort based on values then keys
#[('apple', 1), ('banana', 1), ('orange', 2)]

time complexities

★ hash collision이 없다는 가정 하

+ 추가) checking a key in a dictionary(in operator) O(1) Time Complexity

---

* python set documentation 

* python set geeksforgeeks 

 

* python dictionary documentation 

* python dictionary geeksforgeeks