[바미] 회사에 있는 사람

문제

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

 

코드 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = parseInt(input[0], 10);

const officeLog = new Map();

// 각 로그를 처리
for (let i = 1; i <= n; i++) {
    const [name, action] = input[i].split(' ');
    if (action === 'enter') {
        officeLog.set(name, true);
    } else {
        officeLog.delete(name);
    }
}

// 남아 있는 사람들의 리스트를 사전 역순으로 정렬하여 출력
const remainingPeople = Array.from(officeLog.keys()).sort((a, b) => b.localeCompare(a));
console.log(remainingPeople.join('\n'));

문제 해설

이 문제는 회사에 출근하거나 퇴근한 사람들의 기록을 바탕으로 현재 회사에 남아 있는 사람들의 이름을 사전 역순으로 출력하는 문제입니다. 

 

이 문제 역시 Set을 사용하여 해결했습니다.

출근 시('enter') Set에 추가하고, 퇴근 시 Set('leave')에서 제거하는 아주 간단한 알고리즘입니다.

 

시간 복잡도

입력 처리와 출입 관리 부분에서 각 기록은 한 번씩만 처리되기 때문에 O(N)의 시간 복잡도를 가집니다.

여기서 N은 출입 기록의 수 즉, 입력 데이터의 총 개수를 의미합니다.

 

그리고 최종 정렬 단계에서는 배열의 요소들을 정렬하므로, O(m log m)의 시간 복잡도를 가집니다. 

여기서 m은 현재 회사에 남아 있는 사람의 수입니다.

 

그렇기 때문에 두 단계의 시간 복잡도를 합한 O(n + m log m)이 됩니다.

 

공간 복잡도

Set에 저장되는 이름의 최대 수는 주어진 출입 기록의 총 개수 N에 비례하기 때문에 O(N)의 공간을 사용합니다.

 

그 후 현재 회사에 남아 있는 사람들의 이름을 배열로 변환해야 하므로, 배열도 최대 N개의 요소를 가지게 됩니다. 

 

따라서 O(N)의 공간 복잡도를 가지게 됩니다.