[바미] 듣보잡

문제

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

코드

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

// 첫 번째 줄에서 N과 M을 읽음
const [N, M] = input[0].split(' ').map(Number);

// 듣도 못한 사람들의 이름을 Set에 저장
const unheardSet = new Set(input.slice(1, N + 1));

// 교집합을 찾기 위한 배열 초기화
const unseenUnheard = [];

// 보도 못한 사람들의 이름을 순회하며 교집합 구하기
for (let i = N + 1; i < N + 1 + M; i++) {
    const name = input[i];
    if (unheardSet.has(name)) {
        unseenUnheard.push(name);
    }
}

// 사전 순으로 정렬
unseenUnheard.sort();

// 듣보잡의 수와 명단 출력
console.log(unseenUnheard.length);
console.log(unseenUnheard.join('\n'));

문제 해설

주어진 문제에서는 N개의 듣도 못한 사람들의 이름과 M개의 보도 못한 사람들의 이름이 순서대로 주어집니다.

두 목록에서 모두 속하는 사람, 즉 듣보잡의 수와 그들의 이름을 사전 순으로 출력하는 것이 목표이죠.

 

이를 위해 교집합을 찾아내고, 그 결과를 사전 순으로 출력해야 하는데 이를 위해  Set을 사용하여 해결했습니다.

중복 관리와 검색 속도 때문이죠.

 

시간 복잡도

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

 

먼저 N개의 듣도 못한 사람들의 이름을 읽어와 Set에 저장하는 데 0(N)만큼의 시간이 걸립니다. (Set에 추가하는 데 평균 0(1) 만큼의 시간이 걸리기 때문.)

 

그리고 M개의 보도 못한 사람들의 이름을 하나씩 확인하고 Set에 있는 지 검사하는 데 0(M)이라는 시간이 걸리고, 각 검사에 0(1)만큼의 시간이 걸립니다.

 

그리고 교집합에 있는 이름들을 사전 순으로 정렬하는 데 O(L log L)만큼의 시간이 걸립니다. 여기서 L은 교집합의 크기가 됩니다.

 

따라서 최종 시간 복잡도는 O(N + M + L log L)이 됩니다.

공간 복잡도

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

 

Set에서 듣도 보도 못한 사람들의 이름을 저장하기 위해 사용되어 최대 N개의 이름을 저장하므로 공간 복잡도는 O(N)이 됩니다. 여기서 N은 듣도 못한 사람의 수를 의미합니다.

 

그리고 교집합 배열에 듣보잡의 이름을 저장하기 때문에 공간 복잡도는 O(L)이 됩니다. 여기서 L은 듣보잡의 수를 의미합니다.

 

따라서 최종 공간 복잡도는 O(N + L)이 됩니다.