[파이썬/python] 백준 - 3018 캠프파이어

문제

https://www.acmicpc.net/problem/3018

---

문제 설명

1. N명의 캠프파이어 참가자가 주어진다.
2. E회 만큼 캠프파이어가 진행된다.
   1. 선영이가 캠프파이어를 참가한다면 새로운 노래를 만들고, 다른 사람들은 새로운 노래만 배운다.
   2. 선영이가 캠프파이어를 참가하지 않는다면, 사람들은 서로 아는 노래를 모두 공유한다.
3. 모든 캠프파이어가 진행된 후 선영이가 알고 있는 노래를 전부 아는 사람들을 오름차순으로 출력한다. 

 

---

풀이

선영이가 참가할 때는 참가자들에게 새로 생긴 노래만 추가한다.

선영이가 참가하지 않을 때는 참가자들끼리 서로 노래를 공유해야 한다. 따라서 캠프파이어 각 참가자의 노래를 합집합하여 노래를 통합한다.  

1. 참가자들이 알고 있는 노래를 저장할 people 배열을 생성한다.
2. 매 캠프파이어 마다 선영이가 참가했다면, idx(현재 노래)를 참가자들에게 저장한 후 idx를 증가시킨다.
3. 선영이가 참가하지 않았다면 참가한 사용자들의 노래들을 union(합집합)연산을 통해 합친 후, 새로 갱신한다.
4. 선영이의 노래와 동일하다면, 결과를 출력한다.
   1. 이 때 리스트로 비교하면, 배열의 순서가 다를 때 False를 반환하기 때문에 set() 자료구조로 변형 후 비교했다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())

idx = 1
people = [[] for _ in range(N+1)]
for _ in range(int(input())):
    lst = list(map(int,input().split()))
    length = lst[0]
    lst = sorted(lst[1:])
    if lst[0] == 1:
        for i in range(length):
            people[lst[i]].append(idx)
        idx+=1
    else:
        song = set()
        for i in range(length):
           song = song.union(set(people[lst[i]]))
        
        for i in range(length):
            people[lst[i]] = list(song)

print(1)
for i in range(2,N+1):
    if set(people[i]) == set(people[1]):
        print(i)

---

시간복잡도

• E회만큼 캠프파이어를 진행하고, 각 캠프파이어 당 최대 N명의 사람이 참여한다. 따라서 약 $E*N$회의 시간이 소요된다.
• 최악의 경우 $N = 100, E = 50$이므로 시간복잡도는 약 $O(5000) = O(10^3)$을 가진다.