[바미] 숫자 카드

문제

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

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input[0], 10);
const sangCards = new Set(input[1].split(' ').map(Number)); // 상근이의 숫자 카드들
const M = parseInt(input[2], 10);
const queries = input[3].split(' ').map(Number); // 검색할 숫자들

// 결과 배열 초기화
const result = [];

// 각 숫자에 대해 상근이의 숫자 카드 존재 여부 검사
queries.forEach(query => {
    result.push(sangCards.has(query) ? 1 : 0);
});

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

코드 설명

먼저 상근이의 숫자 카드 수 N, 숫자 카드 배열, 검색할 숫자 수 M, 검색할 숫자 배열을 입력받습니다.

그 후에  숫자 카드를 Set을에 저장하여  중복제거 해줍니다.

 

이제 반복문을 시작하게 되는데 검색 할 숫자 배열을 순회하며 각 숫자가 Set에 존재하는 숫자인지 확인해줍니다.

존재하게 되면 배열에 1을, 존재하지 않으면 0을 추가한 뒤, 배열을 공백으로 구분하여 출력해줍니다.

문제 해설

이 문제는 상근이가 가지고 있는 숫자 카드들 중에서 특정 숫자들이 존재하는지 확인해야 하는 문제입니다.

효율적인 검색 방법을 위해 Set을 사용하여 풀었습니다.

 

Set의 주요 연산인 add, delete, has는 평균적으로 O(1)시간 복잡도를 가지기 때문에 검색이 많이 필요한  상황에서 배열을 사용하는 것보다 훨씬 효율적인 코드를 만들어 낼 수 있습니다.

 

시간 복잡도

상근이의 N개의 숫자 카드를 저장하기 위해 Set자료구조를 사용했죠?

여기서 add연산을 사용했는데 add 연산은 '문제 해설'에서 말씀드렸듯이 평균적으로 O(1)의 시간 복잡도를 가지게 됩니다.

그렇기 때문에 N개의 카드를 하나씩 Set에 추가하는 데 걸리는 시간은 O(N)이 됩니다.

 

그리고 N개의 숫자에 대해 Set에 존재 여부를 확인하는 검색 작업도 있었죠?

Set의 has연산 역시 평균적으로 O(1)의 시간 복잡도를 가지기 때문에 N개의 숫자 각각에 대한 검색 작업의 총 시간은 O(N)이 됩니다.

 

고로 시간복잡도는 O(N)입니다.

공간 복잡도

마찬가지로 상근이의 N개의 숫자 카드를 저장하기 위해 Set자료구조를 사용했죠?
Set은 중복을 허용하지 않는 유니크한 값을 저장하기 때문에 O(N)이라는 공간 복잡도를 가지게 됩니다.

 

입력된 숫자 카드의 개수에 따라 필요한 메모리 공간이 선형적으로 증가한다는 것을 의미하게 되는데 숫자 카드의 수가 증가하면 메모리도 비례하여 증가 됩니다.