백준에서 nodeJS 사용하기 (#04): 해쉬맵 - Map, Object, Set #18870번 #123123

Kyle Lee·2022년 1월 16일

NodeJS로 풀어보는 백준 알고리즘

목록 보기

4/5

1. 서론

보통 알고리즘 테스트에서 해쉬테이블은 무적기와 같은 포지션을 가지고 있습니다.

~~해쉬테이블의 위상에 대한 농담...~~

Javascript에서 해쉬테이블은 어떻게 쓰이는가?

다양한 상황에서 검색 시간복잡도를 O(1)로 만들 수 있다는 점은 매우 매력적으로 느껴집니다.
하지만 자바스크립트는 자체적으로 해쉬테이블 기능을 매서드로 지원하고 있지는 않습니다.
또한 기본적으로 해쉬테이블은 멀티스레드를 사용하지만 자바스크립트는 싱글스레드 언어입니다.
그래서 대부분의 경우 자바스크립트 개발자들은 다른 방법으로 해쉬테이블을 활용해왔습니다.

2. Key/Value 자료구조 : Map, Object, Set

JS에서는 해쉬테이블 대신 해쉬맵 자료구조를 사용합니다.
물론 이 둘에는 차이가 있어서 해쉬테이블 자료구조를 직접 제작해서 사용할 수도 있습니다.

해쉬맵은 Key/Value로 이루어진 자료구조입니다.
JS에서 이와 같은 자료구조를 사용하는 객체는Map, Object, Set이 대표적입니다.

Object

기존의 자바스크립트 개발자들은 보통 객체의 키와 값을 이용해 해쉬맵을 활용하곤 했습니다.
JS Object의 Dynamic Key라고 불리는 방식을 통해 우리는 객체의 키와 값을 하드코딩하지 않고 변수나 반복문 등을 통해 설정할 수 있습니다.

let mapObj = {}
const numbArray = [1, 2, 3, 4, 5]
const nameArray = ["Kyle", "Zoey", "Brian", "Jack", "David"]

for(let i = 0; i < 5; i++) {
  obj[numbArray[i]] = nameArray[i]
}

// 실행결과 : mapObj = {1: 'Kyle', 2: 'Zoey', 3: 'Brian', 4: 'Jack', 5: 'David'}

기존의 Array에서는 인덱스로 숫자만 사용할 수 있었지만, Object를 통해 우리는 키값(인덱스)으로 문자열, 숫자, 심볼을 사용할 수 있다.

(다른 원시값들 역시 사용은 가능하지만, 반환 시에는 전부 문자열로 반환된다.)

let obj = {};
const numbArray = [true, false, null, undefined, 1, "5"];
const nameArray = ["Kyle", "Zoey", "Brian", "Jack", "David", "Chris"];

for (let i = 0; i < 6; i++) {
  obj[numbArray[i]] = nameArray[i];
}

for (let key in obj) {
  console.log(typeof key);
}

// 실행결과 : (6) string  ['1', '5, 'true', 'false', 'null', 'undefined']

Map

하지만 ES6에서 Map이 추가되면서 더이상 Object를 해쉬맵으로 사용하지 않게 되었습니다.

let hashMap = new Map(); // 맵 객체 생성
hashMap.set(key: any, value: any);  // 키, 값 설정
hashMap[key: any] = value: any // 다이나믹 키, 값 설정

hashMap.size; // 사이즈(길이) 값
hashMap.has(key); // 존재 유무 : true or false
hashMap.get(key); // 값 접근

hashMap.keys(); // 키 전부 불러오기
hashMap.values(); // 값 전부 불러오기

hashMap.delete(key); // 해당 키 삭제
hashMap.clear(); // 전체 삭제

// Iteration with deconstructuring (for of)
for (const [key, value] of hashMap) {
	console.log(`${key} = ${value}`);
}

// Iteration with forEach
hashMap.forEach((value, key) => {
	console.log(`${key} = ${value}`);
});

가장 큰 둘의 차이점은 Map의 Key는 문자열 객체 이외에도 모든 타입이 가능하다는 것입니다.
문자열, 심볼, 객체, 함수, 원시값 등 모든 타입을 키 값으로 사용 가능합니다.

(객체를 키로 사용할 경우 주의할 점)

let obj = {cake: 12000}
map.get({cake: 12000}); // 결과 : undefined, 왜냐 obj !== {cake: 12000}
// 이미 생성되어 변수로 선언된 객체와 get 안에서 새로 생성된 객체는 서로 다른 메모리 주소를 참조하고 있기 때문이다.

또한 데이터의 개수도 Map은 size 함수를 통해 바로 얻을 수 있습니다.
게다가 Map은 데이터의 추가와 삭제 시 Object보다 성능이 뛰어나는 장점이 있습니다.

반면, map은 has로 값의 존재유무를 확인하는 것에 그치는 반면, 객체는 findIndex를 통해 객체의 값을 통해 키값에 접근할 수 있다는 점에서 장단점이 있습니다.

그렇기 때문에 각각의 쓰임처에 따라 유연하게 이 둘을 활용해야 합니다.

사진출처 : https://kellis.tistory.com/129

Set

Set 역시 해쉬맵 자료구조에 속하지만 키값이 따로 없고 값 자체를 불러오기 때문에 해쉬맵으로써의 사용가치는 떨어지기 때문에 잘 사용되지 않습니다.

3. 문제 18870번 - 좌표 압축

해당 문제는 주어진 숫자들의 거리(Interval)에 관계 없이 순서로만 치환하는 문제입니다.
하지만 단순히 접근한다면 시간 초과가 발생하여서 숫자의 순서에 접근할 때 훨씬 빠른 방법이 필요합니다.
따라서 정렬된 배열의 인덱스 번호를 활용하면 쉽게 해결이 가능합니다.

Object를 활용한 풀이

"use strict";
let [N, input] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
input = input.split(" ").map(a=>+a);

let copiedArry = [...input];
input = [...new Set(input)];
input.sort((a, b) => {
  return a - b;
});
// 객체를 생성 후 주어진 숫자를 키로, 인덱스를 값으로 저장한다.
let obj = {};
input.forEach((a, idx) => {
  obj[a] = idx;
});
let ANSWER = [];
for (let i = 0; i < copiedArry.length; i++) {
  ANSWER.push(obj[copiedArry[i]]);
}
console.log(ANSWER.join(" "));

Map를 활용한 풀이

"use strict";
let [N, input] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
input = input.split(" ").map(a=>+a);

let copiedArry = [...input];
input = [...new Set(input)];
input.sort((a, b) => {
  return a - b;
});
// 해쉬맵을 생성 후 주어진 숫자를 키로, 인덱스를 값으로 저장한다.
let hashMap = new Map();
input.forEach((a, idx) => {
  hashMap[a] = idx;
  // hashMap.set(a, idx);
});
let ANSWER = [];
for (let i = 0; i < copiedArry.length; i++) {
  ANSWER.push(hashMap[copiedArry[i]]);
}
console.log(ANSWER.join(" "));