[바미] 문자열 집합

문제

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

코드

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

// 1. 첫 번째 줄에서 N과 M을 가져와야 함.
// 2. 집합 S의 문자열을 저장해야함.
// 3. 검사해야 하는 문자열들을 가져와야 함.
// 각 문자열에 대해 집합 S에 포함되어 있는 지 확인 해야함.
// 결과 출력.

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

// 집합 S의 문자열을 'Set'에 저장.
const setS = new Set(input.slice(1, N + 1));

// 검사해야 하는 문자열들을 가져온다.
const queryStrings = input.slice(N + 1, N + M + 1);

// 각 문자열에 대해 집합 S에 포함되어 있는지 확인한다.
let count = 0;
queryStrings.forEach(query => {
   if (setS.has(query)) {
       count++;
   } 
});

console.log(count)

문제 해설

이 문제는 주어진 문자열 집합 S에 각 문자열이 포함되어 있는지 확인하는 문제입니다. 

이 문제를 풀기 위해 Set을 사용하여 해결하였습니다. (집합 S에 같은 문자열이 여러 번 주어지는 경우는 없기 때문.)

 

시간 복잡도

입력 시 발생하게 되는 시간 복잡도는 N개의 문자열을 읽어와 Set에 저장하기 때문에 O(N)이 됩니다.

이 때 최대 길이가 500로 고정되어 있습니다.

 

그리고 검색 시 주어진 M개의 문자열에 대해 Set에 포함되어 있는 지 확인하는 데 걸리는 시간은 O(M)이 됩니다.

Set은 해시 기반의 자료구조이기 때문에 has 메소드로 요소를 찾는 데 평균적으로 O(1 시간이 소모됩니다. 그렇게 때문에 M개의 요소에 대해 각각 존재 여부를 확인하는 데 걸리는 시간은 O(M)이 됩니다.

 

따라서 전체적으로 봤을 때 입력을 처리하고, 검색하는 시간이 합쳐진 O(N+M)을 갖게 됩니다.

공간 복잡도

집합 S의 N개의 문자열을 저장하는 데 O(N)공간이 필요합니다.

 

그리고 Set에 저장된 문자열은 집합 S의 모든 문자열을 포함하기 때문에 O(N) 공간을 차지하게 됩니다.

 

따라서 전체적으로 N개의 문자열을 저장하고 처리하는 데 필요한 공간은 O(N)이 됩니다.