[바미] 수 찾기

문제

 

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

 

코드

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

const N = parseInt(input[0]);
const A = input[1].split(' ').map(Number);
const M = parseInt(input[2]);
const queries = input[3].split(' ').map(Number);

// 배열 A를 해시셋으로 변환
const set = new Set(A);

// 각 쿼리에 대해 결과 출력
const results = queries.map(query => set.has(query) ? 1 : 0);

console.log(results.join('\n'));

 

문제 해설

이 문제는 주어진 배열 A에서 특정 숫자들이 존재하는지 확인하는 문제입니다. 

효율적인 해결을 위해 해시셋을 사용하여 문제를 풀었습니다.

 

따라서, 주어진 배열 A를 해시셋에 저장하고, 확인할 숫자들이 배열 A에 존재하는지 해시셋을 통해 확인하면 끝나는 문제죠.

 

시간 복잡도

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

 

여기서는 해시셋 생성하는 부분과 쿼리를 처리하는 부분을 계산하면 됩니다.

 

먼저 해시셋을 생성할 때를 알아보죠. 배열 A의 크기는 𝑁이고,  배열 A를 해시셋으로 변환하는 과정에서 각 요소를 해시셋에 추가하는 데 𝑂(1) 시간이 소요되기 때문에 배열 A를 해시셋으로 변환하는 데 필요한 시간은 𝑂(𝑁)이 됩니다.

 

두 번째로 쿼리 처하는 부분이 있었죠? 확인할 숫자의 배열 queries의 크기는 𝑀이고, 각 숫자에 대해 해시셋에서 존재 여부를 확인하는 데 𝑂(1)시간이 소요되기 때문에 𝑀개의 숫자에 대해 존재 여부를 확인하는 데 필요한 시간은 𝑂(𝑀)이 됩니다.

 

따라서, 전체 시간 복잡도는 𝑂(𝑁+𝑀)입니다.

공간 복잡도

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

 

배열 A와 배열 queries를 저장하는 데 각각 𝑂(𝑁)과 𝑂(𝑀)의 공간이 필요하고, 배열 A의 모든 요소를 저장하는 해시셋은 𝑂(𝑁)의 공간이 필요합니다.

 

따라서 전체 공간 복잡도는 𝑂(𝑁+𝑀)이 됩니다.