Silver IV 난이도 문제를 C++로 풀이한 내용입니다. 누가 춤을 추는지 추적하여 춤추는 사람의 수를 계산하는 문제입니다.

백준 26069: 붙임성 좋은 총총이

Silver IV 난이도 문제를 C++로 풀이한 내용입니다. 누가 춤을 추는지 추적하여 춤추는 사람의 수를 계산하는 문제입니다.

문제 소개

문제 번호: 26069
문제명: 붙임성 좋은 총총이
난이도: Silver IV
사용 언어: C++
실행 시간: 0 ms
메모리: 2160 KB
문제 요약: 총총이라는 이름을 가진 사람이 특정 만남에 참여하면, 그 만남에 참여한 다른 사람도 춤을 추게 된다. 시간 순서대로 주어지는 만남 정보를 바탕으로 최종적으로 춤을 추는 사람의 수를 계산하는 문제이다.

접근 방법

문제 이해: 문제는 특정 인물(총총이)이 등장하는 만남에 참여하는 모든 사람이 춤을 추게 된다는 규칙을 따르고 있습니다. 이러한 춤의 전파를 시간 순서에 따라 추적해야 합니다.
알고리즘/자료구조: std::unordered_set을 사용했습니다. 집합 자료구조는 중복을 허용하지 않으며, 특정 원소의 존재 여부를 빠르게 확인할 수 있다는 장점이 있습니다.
선택 이유: unordered_set은 사람 이름을 저장하고, 특정 사람이 춤을 추는지 여부를 count() 함수로 O(1) 평균 시간 복잡도로 확인할 수 있습니다. 또한, 새로운 사람의 이름을 insert() 하는 작업도 O(1) 평균 시간 복잡도로 수행할 수 있어, 문제의 요구사항을 효율적으로 처리할 수 있습니다.

풀이 과정

초기화: std::unordered_set<std::string> dance를 선언하고, "ChongChong"이라는 이름을 가진 사람이 처음에 춤을 추고 있다고 초기화합니다.
입력 처리: N개의 만남 정보를 순서대로 입력받습니다. 각 만남은 두 사람의 이름(a, b)으로 구성됩니다.
춤 전파 확인: 입력받은 두 사람의 이름 a 또는 b 중 하나라도 dance 집합에 포함되어 있다면, 이는 총총이 또는 총총이로부터 춤이 전파된 사람과 만난 경우입니다.
새로운 춤꾼 추가: 만약 dance.count(a) 또는 dance.count(b)가 참이면, 만남에 참여한 두 사람 a와 b 모두 dance 집합에 추가합니다. 이는 해당 사람들이 새롭게 춤을 추기 시작했음을 의미합니다.
결과 출력: 모든 만남 처리가 끝난 후, dance 집합의 크기를 출력합니다. 이 크기가 최종적으로 춤을 추는 사람의 총 수입니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    unordered_set<string> dance;
    dance.insert("ChongChong");

    for (int i = 0; i < N; i++) {
        string a, b;
        cin >> a >> b;

        if (dance.count(a) || dance.count(b)) {
            dance.insert(a); // 키던
            dance.insert(b); // 밸류던
        }  // 총총이 등장한 문자열부터 그 아래로 
    }      // 총총이 등장한 문자열에서 총총과 함께 나온 사람이름을 토대로 전파된다 
           // 총총이 등장하기 전 문자열들은 모두 무시가능하다 만남은 시간순서로 입력됐기 때문이다 
    cout << dance.size();
}

ios::sync_with_stdio(false); cin.tie(NULL);: 입출력 속도를 최적화하기 위한 설정입니다.
unordered_set<string> dance;: 춤을 추는 사람들의 이름을 저장할 집합입니다.
dance.insert("ChongChong");: "ChongChong"이 처음에 춤을 추기 시작하는 사람으로 설정됩니다.
if (dance.count(a) || dance.count(b)): 현재 만남에 참여한 두 사람 a 또는 b 중 한 명이라도 이미 춤을 추고 있다면, 이 조건이 참이 됩니다.
dance.insert(a); dance.insert(b);: 위 조건이 참이면, 만남에 참여한 a와 b 모두 춤을 추는 사람들의 집합에 추가됩니다.
cout << dance.size();: 최종적으로 춤을 추는 사람들의 수를 출력합니다.

복잡도 분석

시간 복잡도: O(N)
- N번의 만남에 대해 각각 unordered_set의 count()와 insert() 연산을 수행합니다. 이 연산들은 평균적으로 O(1)의 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도는 O(N)입니다.
공간 복잡도: O(N)
- 최악의 경우, 모든 사람이 서로 다른 이름을 가지고 있고 모든 사람이 춤을 추게 된다면, unordered_set에는 최대 N개의 이름이 저장될 수 있습니다. 따라서 공간 복잡도는 O(N)입니다.

배운 점

unordered_set 자료구조의 효율적인 사용법을 다시 한번 익혔습니다. 특정 원소의 존재 여부를 빠르게 확인하고 새로운 원소를 추가하는 데 효과적이라는 것을 알 수 있었습니다.
문제의 규칙(춤의 전파)을 시간 순서에 따라 정확히 추적하는 것이 중요하다는 것을 배웠습니다.
입력으로 주어지는 정보의 순서가 문제 해결에 중요한 역할을 할 수 있음을 인지했습니다.

백준 26069: 붙임성 좋은 총총이

문제 소개

접근 방법

풀이 과정

코드 설명

복잡도 분석

배운 점

글 수정