해시 ) KEY 값에 문자열을 부여해 데이터를 저장하는 방법

작성일 In Views: Disqus:

코딩 테스트 문제 중에 데이터를 순회화며 결과를 키 값에 저장해야 할 때가 있습니다. 배열의 인덱스처럼 의미를 부여하여 사용하는 것이 아닌 의미를 지닌 키 값에 직접적으로 데이터를 매칭시킬 수 있는 방법이며, 검색에서의 시간복잡도 또한 O(1)로 효율적인 알고리즘입니다.

▪︎ 해시 알고리즘 (Hash)

기본적으로 배열에 key: value 값으로 데이터를 저장하면 구현이 가능합니다.

1
2
3
4
5
6
7
const hashArray = [];

hashArray["bus"] = 5;
hashArray["price"] = 1000;

console.log(hashArray["bus"]); // output: 5
console.log(hashArray); // output: [ "bus": 5, "price": 1000 ]

자바스크립트의 배열은 다른 언어의 배열과는 다릅니다. 다른 언어의 경우는 데이터가 연속적으로 나열되어 구성되는 밀집 배열이고, 자바스크립트는 희소 배열입니다. 즉 여러 개의 자료형을 허락하며 각 자료가 차지하는 메모리 공간 또한 불규칙 할 수 있습니다. 때문에 위의 방식으로도 배열을 만들 수가 있습니다.

그러나 자바스크립트에서는 더 쉽게 테이블을 사용할 수 있게하는 Map이라는 내장 함수가 있습니다. Map에서 제공되는 여러 프로토타입 메서드를 활용하면 해시 구조에서 원하는 기능을 보다 쉽게 사용할 수 있습니다.

▫︎ Map 함수의 여러 메서드

  1. new Map() : 새로운 Map 객체를 만듭니다.
  2. map.set(key, value) : Map 객체 내의 key와 value를 매핑하여 저장합니다.
  3. map.get(key) : Map 객체에서 key에 해당하는 value를 반환합니다.
  4. map.has(key) : Map 객체 내에 key가 존재한다면 true, 존재하지 않는다면 false를 반환합니다.
  5. map.delete(key) : Map 객체 내에서 key와 매핑된 value 모두를 삭제합니다.
  6. map.size : Map 객체의 요소 수를 반환합니다.
  7. map.forEach(callbackFn(key, value)) : 각 value와 key마다 callbackFn을 삽입한 순서대로 실행합니다.

▪︎ Example of Apply 1

Untitled

▫︎ 문제 접근

  1. 각 후보에 대한 데이터를 생성한다.
  2. 각 후보가 투표를 받을 때마다 데이터를 갱신한다.
  3. 가장 큰 값을 가진 후보를 출력합니다.

위 문제에서 후보에 대한 정보를 저장할 때 key 값으로 후보를 지정하는 것이 좋아보입니다. ( 배열의 index에 의미를 부여하여 사용할 수 있지만 가독성이 좋지 않습니다.) Map 객체를 만들고 각 key 값으로 후보를 등록한 뒤 주어진 개표 결과를 순회하며 value를 업데이트 시켜주면 쉽게 풀 수 있습니다. 이후에는 map.forEach 메서드를 통해 Map 객체를 순회하며 가장 높은 value를 지닌 key를 답으로 등록합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solution(s) {
  let answer = "";
  let max = 0;
  let arr = s.split("");
  let map = new Map();

  arr.forEach((el) => map.set(el, map.get(el) + 1 || 1));
  map.forEach((value, key) => {
    if (value > max) {
      answer = key;
      max = value;
    }
  });

  return answer;
}

▪︎ Example of Apply 2

첫 번째 예시 문제가 key : value 형태로 데이터를 저장하기 위해 Map을 사용했다면, 이번 예시는 key에 접근할 때 효율성을 높여 시간복잡도를 줄이기 위해 적용하는 문제 예시를 보겠습니다.

image.png

image.png

위 문제는 [4, 1, 5, 2, 3] / [1, 3, 7, 9, 5] 두 배열을 순회하여 겹치는지 확인만하면 되는 간단한 문제입니다. 그런데 N의 입력값 범위를 살펴보면

1 ≤ N ≤ 100,000 으로 이중 순회로 구현하여 O(n^2)의 시간복잡도로 풀 경우, 시간 제한에 걸리게 됩니다. Map 내장 함수의 경우 key에 접글할 때 O(1)의 시간복잡도를 가지기 때문에 하나의 배열을 Map으로 만들고 나머지 배열 하나를 순회하며 Map에 key 값이 있는지 여부만 판단하면 조건에 맞게 풀 수 있습니다.

  • 이중 순회로 구현 (시간 초과)
1
2
3
4
5
6
7
8
const fs = require("fs");
const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const N = input[1].split(" ").map((v) => +v);
const M = input[3].split(" ").map((v) => +v);

for (let i = 0; i < M.length; i++) {
  N.includes(M[i]) ? console.log(1) : console.log(0);
}
  • array.prototype.includes() 메서드는 O(N)의 시간복잡도를 가진다.
  • Map 함수 적용하여 구현 (조건 통과)
1
2
3
4
5
6
7
8
const fs = require("fs");
const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const N = input[1].split(" ").map((v) => +v);
const M = input[3].split(" ").map((v) => +v);
const map = new Map();

N.forEach((el) => map.set(el, true));
M.forEach((el) => (map.has(el) ? console.log(1) : console.log(0)));