붙임성 좋은 총총이

문제

 

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0], 10);
const connections = input.slice(1);

const danceSet = newSet(); // Set을 생성할 때 new Set()으로 생성합니다.
danceSet.add('ChongChong');

// 각 사람의 연결 관계를 탐색for (let i = 0; i < N; i++) {
    const [A, B] = connections[i].split(' ');

    // A 또는 B가 무지개 댄스를 추고 있으면, 다른 사람도 추게 된다.if (danceSet.has(A) || danceSet.has(B)) {
        danceSet.add(A);
        danceSet.add(B);
    }
}

console.log(danceSet.size);

문제 해설

이 문제는 총총이(ChongChong)를 만난 모든 사람들이 무지개 댄스를 추게 되는 상황을 시뮬레이션하는 문제입니다.

 

무지개 댄스를 추는 사람들을 관리하기 위해 집합(Set)을 사용했습니다.

Set은 중복을 허용하지 않는 특성이 있어 효율적으로 요소를 추가하고,  요소들을 조회할 수 있기 때문입니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

먼저 입력을 처리하는 데 𝑂(𝑁)시간이 필요합니다. 여기서 𝑁은 만남 기록의 수입니다.
그리고 각 기록에 대해 두 사람의 이름을 Set에서 검사하고, 필요시 추가하는 작업의 시간이 있는데 이는 𝑂(1) 시간에 수행됩니다.

따라서 전체 시간 복잡도는 𝑂(𝑁)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

주어진 입력(만남 기록)을 저장하는 데 𝑂(𝑁)의 공간이 필요하고, 무지개 댄스를 추게 된 사람들을 저장하는 Set이 있는데 이 Set은 최대 𝑂(𝐾)의 공간을 사용합니다. 이 때 𝐾는 사람들이 만나는 모든 이름의 개수를 의미합니다.

 

따라서 전체 공간 복잡도는 𝑂(𝑁+𝐾)가 됩니다.