[프로그래머스 / JavaScript] 해시(Hash) (ft. js의 Map과 Set)

 

프로그래머스의 코딩테스트 고득점 Kit를 풀어보기 시작했다. 그 중 "해시" 유형의 문제들을 풀어보면서 알게 된 여러가지 내용들을 정리해보려고 한다. 먼저, 해시(Hash)의 개념부터 알아보도록 하자.

 

 

 

---

 

 

 

해시(Hash)의 개념

데이터를 효율적으로 관리하기 위해 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 매핑하는 것을 해시(Hash)라고 한다.

• 키(Key) : 매핑 전 원래 데이터의 값
• 해시값(Hash Value) : 매핑 후 데이터의 값
• 해싱(Hashing) : 매핑하는 과정
• 해시함수(Hash Function) : 키에 대한 해시값을 구하기 위해 사용하는 함수(알고리즘)

쉽게 말해, key-value로 이루어진 자료구조라고 생각하면 된다.

해시값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1) 로 매우 빠르다. 

 

매핑(mapping)
매핑이란 어떤 값을 다른 값에 대응시키는 과정을 말한다. 프로그래밍에서 매핑은 키(key) 역할을 하는 데이터와 값(value) 역할을 하는 데이터를 짝 지어(=연결 지어) 저장하는 데이터 구조를 말한다.

 

이와 관련해서 해시 테이블(Hash Table)과 해시 함수(Hash Function)는 추후 다시 정리해보려고 한다.

 

 

 

문제

https://programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

 

 

 

풀이과정

문제를 해결하기 위해서 아래의 사항을 고려해야 한다.

1. 연구실에 있는 총 N마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다.
2. 최대한 많은 종류의 폰켓몬을 가져갈 수 있도록 한다.

해당 문제는 해시(Hash)를 이용해서 풀어야하기 때문에 Map을 사용해서 풀어보도록 하겠다.

풀이를 하기 전에 Map에 대해 정리해보자.

 

 

 

Map이란?

Map은 데이터와 키를 같이 저장할 수 있는 자료구조이다. 키가 있는 데이터를 저장한다는 점에서 객체(Object)와 유사하지만, 객체의 key는 문자열(String)만 사용 가능하지만 맵(Map)은 다양한 자료형을 허용한다는 차이가 있다.

 

 

Map을 사용하는 이유

Map을 사용하면 데이터를 쉽게 추가, 조회, 수정, 삭제할 수 있으며, 순서가 보장되는 순회(iteration)도 가능하다. 그래서 key-value를 보다 효율적으로 관리하고 검색할 때 사용할 수 있다.

이 외에도 Map은 아래와 같은 특징을 가진다.

 

 

|  검색 속도

Map은 해시 맵(Hash Map, 쉽게 말해서 Key-Value의 구조)의 구조를 사용하여 데이터를 저장하므로 특정 키로 값을 검색할 때 빠른 검색 속도를 제공한다. 해시 맵은 일반적으로 평균 O(1)의 시간 복잡도를 가지며, key의 해시 값을 계산해 원하는 값을 바로 찾을 수 있다.

 

|  중복 key 처리

Map은 중복된 키를 허용하지 않는다. 중복된 키를 삽입하려고 하면 기존의 값이 덮어 씌워진다. 따라서 데이터의 중복을 방지할 수 있다.

 

|  순서 보장

Map은 key-value 쌍을 삽입한 순서대로 보장한다. 따라서 데이터의 순서가 중요할 경우 Map을 사용하면 데이터를 순서대로 처리할 수 있다.

 

|  원시 타입 및 객체 타입 모두 사용 가능

Map은 key로 원시 타입뿐만 아니라 객체, 함수 등 다양한 데이터 타입을 사용할 수 있다.

 

|  반복과 관련된 효율성

Map은 for...of 나 forEach 메서드를 사용해 효율적으로 데이터를 순회할 수 있다. 그래서 for 루프를 사용할때 보다 더욱 간결하게 코드를 작성할 수 있다.

 

 

Map의 주요 메서드와 프로퍼티

new Map(); // Map 생성하기

map.set(key, value); // key를 이용해 value를 저장

map.get(key); // key에 해당하는 값 반환. key가 존재하지 않는다면 undefined 반환

map.set(key, newValue); // 값 수정하기

map.has(key); // key가 존재하면 true, 존재하지 않으면 false 반환

map. delete(key); // key에 해당하는 값 삭제

map.clear(); // Map 안의 모든 요소 제거

map.size; // Map 크기 확인(요소의 개수 반환)

// Map 순회하기
for (const [key, value] of map) {
  console.log(`key: ${key}, value: ${value}`);
}

// key를 대상으로 순회하며, 각 요소의 key를 모은 iterable 객체를 반환
for (let key of map.keys()) {
  console.log(key);
}

// value를 대상으로 순회하며, 각 요소의 value를 모은 iterable 객체를 반환
for (let value of map.values()) {
  console.log(value);
}

// 요소의 [key,value] 한 쌍으로 하는 iterable 객체를 반환. 이 객체는 for...of 루프의 기초로 쓰인다.
for (let [key, value] of map.entries()) {
  console.log(`${key} : ${value}`);
}

// 배열과 유사하게 내장 메서드인 forEach 반복문을 지원한다.
map.forEach((value, key, map) => {
  console.log(`${key} : ${value}`);
});

 

 

Map을 이용해서 풀어 본 답안

function solution(nums) {
  let map = new Map();
  let myPokemon = nums.length / 2;
  
  for (let i = 0; i < nums.length; i++) {
    map[nums[i]] = (map[nums[i]] || 0) + 1;
  }
  
  let objLength = Object.keys(map).length;
  
  return objLength <= myPokemon ? objLength : myPokemon;
}

위의 코드를 해석하자면,

1. 먼저, 빈 객체 'map'을 생성한다. 이 객체는 배열 'nums'에서 각 요소의 등장 횟수를 추적한다.
2. 변수 'myPokemon'에 배열 'nums'의 길이를 2로 나눈 정수 값을 저장한다. (N/2 마리)
3. for문을 사용하여 배열 'nums'의 각 요소를 순회한다. 루프 내에서 현재 요소 nums[i]를 'map' 객체에 추가하거나 갱신한다. map[nums[i]]는 현재 요소의 등장 횟수를 나타내며, 이 값이 이미 존재하면 기존 값에 1을 더하고, 없다면 1로 초기화한다.
4. 'Object.keys(map)'을 사용하여 'map' 객체의 속성 키들을 배열로 추출하고, 이 배열의 길이를 'objLength' 변수에 저장한다. 이렇게 하면 배열 'nums'에서 서로 다른 요소의 개수를 알 수 있다.
5. 삼항 연산자를 사용하여 'objLength'와 'myPokemon'을 비교하여 'objLength'가 'myPokemon'보다 작으면 'objLength'를 반환하고, 그렇지 않으면 'myPokemon'을 반환한다.

 

 

 

---

 

 

 

문제를 풀고나니, 실직적으로 Map 안의 값을 사용하지 않는데 굳이 해시(Hash)를 할 필요가 있을까? 라는 의문이 들었다. 일단 해시를 통해 데이터를 정리하면 O(n)만큼의 시간이 들기 때문이다.

그래서 여러 다른 풀이 과정들도 찾아보다가 Set 함수를 이용해서 중복 없이 폰켓몬을 정리하면 그 값이 곧 폰켓몬의 종류가 된다는 사실을 깨달았다.

 

 

Set이란?

Set은 중복이 존재할 수 없는 자료구조이다. 키가 없는 값을 저장한다는 점에서 배열(Array)와 유사하지만, 값을 조회하는 데에 있어서 Array에 비해 훨씬 빠르다.

 

 

Set을 사용하는 이유

Set은 중복 요소를 허용하지 않기 때문에 Set 내에서 동일한 값을 여러번 저장할 수 없다. 또한, 요소를 추가한 순서대로 저장하며, 요소를 순회할 때 이 순서를 유지한다.

따라서 Set을 사용하면 아래와 같은 이점이 있다.

 

 

|  중복 제거

값의 중복 요소를 제거하고자 할 때 Set을 활용할 수 있다. 요소를 Set에 추가하면 자동으로 중복이 제거된다.

 

|  빠른 검색

Set은 배열(Array)에 비해 요소를 빠르게 검색할 수 있다. 배열의 값은 다양한 타입이 오기도 하고, 중복되는 값이 존재할 수 있다. Set은 이와 달리 중복되지 않은 값들을 모아둔 콜렉션이다. 따라서 여러 개의 값들을 나열한 배열(Array)에 비해 요소의 존재 여부를 조회하는 속도가 훨씬 빠르다.

 

|  고유한 값 추적

고유한 값을 추적하거나 고유한 요소의 개수를 세는 데 유용하다. 예를 들어, 중복되지 않은 값의 개수를 셀 때 유용하다.

 

|  집합 연산

Set은 합집합, 교집합, 차집합 등의 집합 연산을 쉽게 구현할 수 있다.

 

|  반복 가능(iterable)

Set은 반복 가능한 객체(iterable)이므로 for...if문이나 forEach 메서드를 사용해서 요소를 순회할 수 있다.

 

 

Set의 주요 메서드와 프로퍼티

new Set(); // Set 객체 생성하기

set.add(value); // 값 추가하기

set.delete(value); // 값 제거하기. 삭제되었으면 ture, 값이 없거나 삭제되지 않으면 false 반환

set.has(value); // Set 내에 값이 존재하면 true, 존재하지 않으면 false 반환

set.clear(); // 모든 값 삭제하기

set.size; // Set 객체 안에 있는 요소의 개수를 반환

// Set 순회하기
for (const value of set) {
  console.log(`value: ${value}`);
}

// key를 대상으로 순회하며, Set 내의 모든 값을 포함하는 iterable 객체를 반환
for (const key of set.keys()) {
  console.log(key);
}

// set.keys와 동일한 작업 수행. Map과의 호환성을 위해 만들어진 메서드
for (const value of set.values()) {
  console.log(value);
}

// Set 내의 각 값을 이용해 만든 [value, value] 배열을 포함하는 이터러블 객체를 반환. 
// Map과의 호환성을 위해 만들어진 메서드
for (const data of set.entries()) {
  console.log(data);
}

// Set의 내장 메서드로 forEach 반복문 지원. Map과의 호환성을 위해 콜백 변수가 3개이며, 
// 두번째 valueAgain은 첫번째 value와 동일한 값을 반환
set.forEach((value, valueAgain, set) => {
  console.log(`${value} : ${valueAgain}`);
});

 

 

Set을 이용해서 풀어 본 답안

function solution(nums) {
  let myPokemon = nums.length / 2;
  let set = new Set(nums);
  let maxNum = set.size;
  
  return myPokemon <= maxNum ? myPokemon : maxNum;
}

 

 

 

 

 

[참고자료]

[ES6+] Map(), Set() 객체의 특징과 사용법

[프로그래머스] 폰켓몬 ( by using JavaScript )

[JavaScript] 37. Set 과 Map