[백준 10816번] 숫자 카드 2 - JavaScript

 

 

이제는 문제를 보고 사용될 알고리즘도 같이 보기 시작했다.

 

이 문제에서는 사용된 알고리즘으로 아래와 같이 표시되어 있다.

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵

 

이분 탐색과 정렬은 정렬하여 이진 탐색을 통해 요소를 찾는구나 싶었지만 해시를 사용한 집합과 맵은 도대체 왜 사용해야하는지 이해가 되지 않았다.

 

그래서 해시와 맵을 찾아본 결과 해시는 간단히 설명하자면 키-값으로 이루어진 자료구조고, 배열과 다르게 키 값으로 문자열이 올 수 있다는 것이었다.

또한 집합은 요소들의 중복을 금지하기에 어떻게 이 두 가지 자료구조를 활용할지 생각이 나지 않았다.

 

그러던 도중 집합으로 만들되, 숫자를 키로, 각 요소의 개수를 값으로 하는 해시맵을 만들어 사용하면 어떨까 ? 라는 생각이 들었다.

 

 

그러니까 10 - 3 이런 식으로 저장되는 것이다.

해시맵을 사용하면 저장된 데이터에 대해 O(1)의 시간 복잡도를 가지므로 이 방법이 문제에서 의도한 방법이라는 생각이 들었다.

따라서 코드에서 상근이가 가지고 있는 숫자 카드들을 카드 종류 - 해당 카드 개수 로 해시맵(hashMap)에 저장하였다.

 

그리고 개수를 구할 카드에 대해 해시맵에서 개수를 구하도록 하였다.

 

소스코드

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

const num = input.shift();
const data = input
	.shift()
	.split(' ')
	.map(Number)
	.sort((a, b) => a - b);

var hashMap = new Map();

data.forEach((value) => {
	hashMap.set(value, (hashMap.get(value) || 0) + 1);
});

const reqDataNum = input.shift();

const reqData = input.shift().split(' ').map(Number);

const result = reqData.map((num) => hashMap.get(num) || 0);

console.log(result.join(' '));

 

자료구조를 이렇게 활용하는거구나.