3018번 - 캠프파이어

💡 이번에도 Set의 중요성을 한번 더 깨우쳤다!!

N = int(input())
E = int(input())

array = [[0] for _ in range(N+1)]
last = 0

for _ in range(E):
    
    schedule = list(map(int,input().split(' ')))
    
    # 선영이가 포함되어 있다면
    if 1 in schedule[1:]:
        for i in range(1,schedule[0]+1):
            array[schedule[i]].append(last+1)
        last += 1

    # 선영이가 포함되어 있지 않다면
    else:
        total = []
        for j in range(1,schedule[0]+1):
            total += array[schedule[j]]
        
        for k in range(1, schedule[0]+1):
            array[schedule[k]] = list(set(total))

for idx,val in enumerate(array):
    
    if val == array[1]:
        print(idx)

• 사실 처음에 문제를 정확하게 이해하지 못해서 시간이 꽤 걸린 문제였다..ㅎ
• 선영이가 포함되어야지 노래가 1개씩 추가된다는 점이 중요했다.
• 어려웠던 건 선영이가 포함되지 않는 경우 참여하는 사람들의 보유 노래를 전부 공유하는 부분 이였다

💡 선영이가 포함되는 경우
새로운 노래 (last + 1)을 참여하는 참가자들에게 부여

💡 선영이가 포함되지 않는 경우
total이라는 새로운 리스트에 각 사람들이 소유한 노래를 모아서, set으로 중복제거 후,
다시 사용하기 쉽게 list로 변환하고, 각 리스트에 넣어준다.

    # 선영이가 포함되어 있다면
    if 1 in schedule[1:]:
        for i in range(1,schedule[0]+1):
            array[schedule[i]].append(last+1)
        last += 1

    # 선영이가 포함되어 있지 않다면
    else:
        total = []
        for j in range(1,schedule[0]+1):
            total += array[schedule[j]]
        
        for k in range(1, schedule[0]+1):
            array[schedule[k]] = list(set(total))            

오프라인 코테 스터디 (12/30)
참가 인원: 기우석님

• 풀이 방식

for (int l = 0; l < e; l++) {
        int num;
        cin >> num;
        vector<int> tmp_arr(num);
        bool hasSunyoung = false;
        for (int i = 0; i < num; i++) {
            cin >> tmp_arr[i];
            if (tmp_arr[i] == 1)
                hasSunyoung = true;
        }
        if (hasSunyoung) {
            for (int person : tmp_arr) {
//                save[count].push_back(person);
                mem[person].push_back(count);
            }
            count++;
        }
        else {
            set<int> sharedSongs;
            for (int person : tmp_arr) {
                for (int song : mem[person]) {
                    sharedSongs.insert(song);
                }
            }
            for (int person : tmp_arr) {
                for (int song : sharedSongs) {
                    mem[person].push_back(song);
                }
            }
        }
    }
    // 각 mem 배열에서 중복 제거
    for (int i = 1; i <= n; i++) {
        sort(mem[i].begin(), mem[i].end());
        mem[i].erase(unique(mem[i].begin(), mem[i].end()), mem[i].end());
    }
    // 모든 노래를 아는 사람 찾기
    set<int> allSongs;
    for (int i = 1; i < count; i++) {
        allSongs.insert(i);
    }
    vector<int> allKnownPeople;
    for (int i = 1; i <= n; i++) {
        set<int> personSongs(mem[i].begin(), mem[i].end());
        if (includes(personSongs.begin(), personSongs.end(), allSongs.begin(), allSongs.end())) {
            allKnownPeople.push_back(i);
        }
    }