[바미] 숫자 카드 2

문제

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

코드

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

// 첫 번째 줄에서 N을 추출
const N = parseInt(input[0], 10);

// 두 번째 줄에서 숫자 카드에 적힌 정수들 추출
const sangCards = input[1].split(' ').map(Number);

// 세 번째 줄에서 M을 추출
const M = parseInt(input[2], 10);

// 네 번째 줄에서 찾을 숫자들을 추출
const queries = input[3].split(' ').map(Number);

// 숫자 카드의 개수를 카운트하기 위한 맵
const cardCountMap = new Map();

// 각 숫자 카드에 대해 개수 카운트
sangCards.forEach(card => {
    cardCountMap.set(card, (cardCountMap.get(card) || 0) + 1);
});

// 각 확인해야 하는 숫자에 대해 결과 생성
const result = queries.map(query => cardCountMap.get(query) || 0);

// 결과 출력
console.log(result.join(' '));

 

문제 해설

이 문제에서는 상근이가 가지고 있는 숫자 카드의 개수를 효율적으로 찾아야 합니다.

카드 값을 저장하고, 효율적으로 검색하기 위해 이 문제 역시 해시맵을 사용하여 문제를 해결하였습니다.

 

시간 복잡도

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

먼저 숫자 카드 N개의 각 숫자를 해시맵에 기록해야 하는데 이 때 해시맵의 set 연산은 평균적으로 O(1) 시간이 걸리므로, N개의 숫자 카드를 해시맵에 모두 기록하는 데 O(N) 시간이 소요됩니다.

 

그리고 M개의 쿼리 검색에 필요한 시간이 필요합니다. 이 때 소비되는 시간은 평균적으로 O(1)시간이 소요 되는데 M개의 숫자에 대해 검색하는 작업은 총 O(M) 시간이 소요됩니다.

 

따라서 전체 시간 복잡도는 O(N + M)이 됩니다. 여기서 N은 상근이가 가지고 있는 숫자 카드의 개수이고, M은 찾으려는 숫자의 개수입니다.

공간 복잡도

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

 

해시맵에 필요한 공간만 계산하면 됩니다. 해시맵에는 N개의 숫자 카드에 대한 개수를 저장해야 하는데 이 때 숫자 카드가 중복되더라도 모든 숫자 카드에 대해 해시맵에 하나의 엔트리를 할당하게 됩니다.

 

즉, 최대 N개의 숫자 카드에 대한 개수를 저장해야 하므로 O(N)의 공간이 필요합니다.

 

따라서 공간 복잡도는 O(N)가 됩니다.