[백준] 14425 문자열 집합 Node.js

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

예제 입력 1

5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink

예제 출력 1

4

---

문제풀이

❌ 오답: 시간 초과

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, ...input] = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = N.split(' ').map(Number);
let result = 0;

for (let i = 0; i < n; i++) {
  for (let j = n; j < n + m; j++) {
    if (input[i] === input[j]) result++;
  }
}

console.log(result);

• 이중 반복문을 사용하여 모든 가능한 조합을 비교합니다. 바깥쪽 반복문은 첫 번째 문자열 집합을 반복하고, 안쪽 반복문은 두 번째 문자열 집합을 반복하여 일치하는 경우를 찾습니다. 이는 문자열 집합의 크기가 커질수록 시간 복잡도가 O(N*M)이 됩니다. 따라서 입력의 크기가 큰 경우 시간 초과가 발생합니다.

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, ...input] = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = N.split(' ').map(Number);
const target = new Set(input.slice(0, n));
let result = 0;

for (let j = n; j < n + m; j++) {
  if (target.has(input[j])) result++;
}

console.log(result);

• Set()을 이용하여 비교하는 방법으로 해결할 수 있습니다. Set을 사용하여 첫 번째 문자열 집합을 저장합니다. 그런 다음 두 번째 문자열 집합을 반복하면서 Set에 있는지 확인하는 방식을 사용합니다. 이 방법은 두 번째 문자열 집합의 크기에 비례하는 O(M)의 시간 복잡도를 가집니다.