[알고리즘/백준] 26069번 - 붙임성 좋은 총총이

🔗 문제 

26069번: 붙임성 좋은 총총이

level : 실버 4
문제 설명: 무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다.기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이(ChongChong) 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자!

---

🔮 풀이 아이디어

defaultdict(int)로 딕셔너리를 선언해주면 key가 존재하지 않아도 접근할 경우 key를 만들어준 후 key에 해당하는 값을 int로 지정하여 0으로 초기화를 해준다.

그 점을 이용하여 각 사람의 이름을 딕셔너리의 key로 활용하여 두 사람(nameA, nameB) 둘 중 한명이라도 춤을 추고 있을 경우, 두 사람의 상태를 춤을 추는 상태(1)로 변경해준다.

마지막에 딕셔너리의 값이 춤을 추는 상태(1)인 경우를 count 함수를 활용하여 출력해준다.

 

최종 제출 코드

 

import sys
from collections import defaultdict
input = sys.stdin.readline

N = int(input())
people = defaultdict(bool)
people["ChongChong"] = True # 춤을 추고 있는 상태

for _ in range(N):
    nameA, nameB = input().split()
    if people[nameA] is True or people[nameB] is True:
        people[nameB] = people[nameA] = True

print(list(people.values()).count(True))

---

📝 새로 공부한 내용

다른 사람의 풀이

import sys

input = sys.stdin.readline
n = int(input().strip())
dancing = set(['ChongChong'])
for i in range(n):
    a, b = input().split()
    if a in dancing:
        dancing.add(b)
    if b in dancing:
        dancing.add(a)
print(len(dancing))

 

다른 분의 풀이를 통해 set을 활용하여 풀 수 있다는 것도 알 수 있었다.
내가 생각했을 때 집합 안의 모든 원소에서 특정 이름이 들어간 경우를 찾는 것이 더 오래 걸릴 것이라 생각해 dict를 사용했는데 시간을 보니 set을 활용한 코드의 시간이 더 빨랐다.

 

그 이유는 set에서의 x in s 연산의 평균 시간 복잡도는 O(1) 이라고 한다.

파이썬에서 set은 hash table로 구현되어 있기 때문이었다..!

 

근데 dictionary 또한 hash table로 구현되어있다..!
추가적으로 아마 defaultdict를 써서 조금 더 시간이 오래걸리지 않았을까 싶다.

---

📚 참고

[Python] 세트(set)의 시간 복잡도
[Python] 리스트와 딕셔너리의 주요 연산 시간 복잡도