[바미] 인사성 밝은 곰곰이

문제

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

 

코드

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

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

let greetingCount = 0;
let enteredUsers = new Set();

for (const record of records) {
    if (record === 'ENTER') {
        // 새로운 사람이 입장하면, Set을 초기화하여 새로운 그룹을 시작한다.
        enteredUsers = new Set();
    } else {
        if (!enteredUsers.has(record)) {
            // 새로운 닉네임이라면 곰곰티콘으로 인사한 것으로 간주하고, 카운트를 증가시킨다.
            greetingCount += 1;
            enteredUsers.add(record);
        }
    }
}

console.log(greetingCount);

 

문제 해설

이 문제는 주어진 채팅 기록에서 새로운 사람이 입장한 후 처음으로 채팅을 입력한 사람을 찾고, 그들이 곰곰티콘을 사용했다고 가정하는 문제입니다. 이를 해결하기 위해 다음 단계로 접근할 수 있습니다.

 

1. 새로운 사람이 입장할 때마다 그 그룹을 초기화합니다.
2. 그룹 내에서 첫 번째로 채팅을 입력하는 사람들을 추적합니다.
3. 이러한 사람들의 수를 세어 곰곰티콘 사용 횟수를 계산합니다.

따라서 아래와 같은 순서로 코드가 실행됩니다.

1. 채팅 기록 수와 채팅 기록을 입력으로 받습니다.
2. 변수들을 초기화합니다.
3. 각 채팅 기록을 순회하며 새로운 그룹과 새로운 사용자들을 추적합니다.
4. 곰곰티콘 사용 횟수를 출력합니다.

 

시간 복잡도

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

 

parseInt(input[0], 10)와 input.slice(1)는 각각 𝑂(1)과 𝑂(𝑁)시간이 걸리게 되고, 각 기록을 순회하며 ENTER와 닉네임을 처리 하는데 𝑂(𝑁)시간이 걸리게 됩니다.

 

그리고 Set을 사용하여 닉네임의 존재 여부를 확인하고 추가하는 작업은 평균적으로 𝑂(1) 시간이 걸립니다.

따라서, 전체 시간 복잡도는 주어진 채팅 기록의 수 𝑁에 비례하는 𝑂(𝑁) 시간이 걸리게 됩니다.

공간 복잡도

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

 

greetingCount 변수는 𝑂(1)공간을 차지하게 되고, enteredUsers 집합은 최악의 경우 𝑁개의 닉네임을 저장할 수 있으므로

𝑂(𝑁)의 공간을 차지하게 됩니다.

 

따라서 전체 공간 복잡도는 O(N)이 됩니다.