728x90
반응형
문제
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)이 됩니다.
728x90
반응형
'하루 알고리즘(JS)' 카테고리의 다른 글
[바미] 나는야 포켓몬 마스터 이다솜 (0) | 2024.05.05 |
---|---|
[바미] 회사에 있는 사람 (0) | 2024.05.04 |
[바미] 숫자 카드 (0) | 2024.05.02 |
[바미] 좌표 압축 (0) | 2024.05.01 |
[바미] 나이순 정렬 (0) | 2024.04.30 |