TIL. 해쉬맵 알고리즘 문제풀이

해쉬맵(HashMap)

해쉬맵은 키-값 쌍을 저장하는 자료 구조로, 해시 함수를 사용하여 키를 해시코드로 변환하고, 이 해시코드를 사용하여 값을 저장하고 검색한다. 해쉬맵은 데이터를 빠르게 저장하고 검색할 수 있도록 설계된 효율적인 자료구조이다.

해쉬맵의 특징

키-값 쌍의 저장
해쉬맵은 데이터를 키-값 쌍으로 저장한다. 각 키는 고유해야 하며, 하나의 키는 하나의 값을 가리킨다.

해시 함수 사용
해쉬맵은 키를 해시코드로 변환하기 위해 해시 함수를 사용한다. 해시 함수는 키를 해쉬 테이블 내의 인덱스로 변환한다.

빠른 접근 속도
해시 함수의 결과를 사용하여 키-값 쌍을 빠르게 저장하고 검색할 수 있다. 이론적으로, 해쉬맵의 저장, 검색, 삭제 연산은 평균적으로 O(1) 시간 복잡도를 가진다.

해시 충돌
두 개 이상의 키가 같은 해시코드를 가지는 경우를 해시 충돌이라고 한다. 해쉬맵은 이러한 충돌을 처리하기 위해 여러 가지 방법(예: 체이닝, 오픈 어드레싱)을 사용한다.

순서 보장 없음 해쉬맵은 키-값 쌍을 저장할 때 키의 순서를 보장하지 않는다. 즉, 데이터를 넣은 순서대로 데이터가 저장되거나 검색되지 않을 수 있다.

사용 예

해쉬맵은 데이터베이스 캐싱, 유일한 객체 관리, 빠른 데이터 검색 등 여러 분야에서 널리 사용된다. 예를 들어, 사용자 ID와 사용자 정보를 매핑할 때 해쉬맵을 사용하면, 특정 ID에 대한 사용자 정보를 매우 빠르게 검색할 수 있다.

해쉬맵을 사용해야 하는 알고리즘 문제의 예시로는 주로 데이터의 빠른 접근이 필요한 경우가 있다. 해쉬맵은 키를 통해 빠르게 해당 값을 찾을 수 있어, 데이터 검색, 중복 확인, 빈도 수 계산 등에 유용하다. 😄

예시) 문자열 내 문자 빈도수 계산

문제
: 주어진 문자열에서 각 문자가 몇 번 등장하는지를 계산하라.

해결 방법
:빈 해쉬맵을 생성한다.
문자열을 순회하며 각 문자를 키로 사용한다.
해쉬맵에서 해당 문자를 키로 하는 값을 찾는다.
만약 키가 존재한다면, 그 값을 1 증가시킨다.
존재하지 않는다면, 새로운 키-값 쌍을 추가하고 값을 1로 설정한다.
해쉬맵에 저장된 키-값 쌍을 사용하여 결과를 반환한다.

function countCharacterFrequency(str) {
    const frequencyMap = {};
    for (const char of str) {
        if (frequencyMap[char]) {
            frequencyMap[char] += 1;
        } else {
            frequencyMap[char] = 1;
        }
    }
    return frequencyMap;
}

const str = "hello world";
console.log(countCharacterFrequency(str));

학급 회장

문제 설명

학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다. 투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다. 선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작 성하세요. 반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.

▣ 입력설명
첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다.
두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 입력됩니다.

▣ 출력설명
학급 회장으로 선택된 기호를 출력합니다.

▣ 입출력 예

input	output
BACBACCACCBDEDE	C

풀이

const pickClassPresident = (str) => {
  let i = 0;
  let obj = {};

  while (i < str.length) {
    obj[str[i]] = obj[str[i]] ? obj[str[i]] + 1 : 1;
    i++;
  }

  let max = 0;
  let answer = '';
  for (x in obj) {
    if (max < obj[x]) {
      max = obj[x];
      answer = x;
    }
  }

  return answer;
};

let str = 'BACBACCACCBDEDE';
console.log(pickClassPresident(str));

👉 객체를 이용하여 풀어보기!

• while 루프를 사용하여 입력받은 문자열 str의 각 문자에 대해 반복한다.
• obj[str[i]] = obj[str[i]] ? obj[str[i]] + 1 : 1 코드를 통해 obj 객체에서 각 문자(후보의 기호)의 등장 횟수를 계산한다.

• 가장 많은 표를 얻은 후보 찾기
  max 변수를 사용하여 현재까지 발견된 가장 많은 표의 수를 추적한다.
  for...in 루프를 사용하여 obj 객체의 각 속성(후보의 기호)을 반복하면서, 해당 후보가 얻은 표의 수obj[x]를 확인한다.
  만약 현재 후보의 표 수가 max보다 많다면, max를 해당 표 수로 업데이트하고 answer에 해당 후보의 기호를 저장한다.

📌 JavaScript에서 객체{}를 사용하여 각 후보의 표 수를 저장하고 관리하는 부분이 해쉬맵의 역할을 한다! 😀
JavaScript의 객체는 내부적으로 해시 테이블을 사용하여 키-값 쌍을 관리하기 때문에, 이를 해쉬맵의 일종으로 볼 수 있다고 한다.

👉 개선하기

const pickClassPresident = (str) => {
  let obj = {};

  for (let x of str) {
    obj[x] = obj[x] ? obj[x] + 1 : 1;
  }

  let answer = Object.entries(obj).reduce((a, b) =>
    a[1] > b[1] ? a : b
  )[0];

  return answer;
};

let str = 'BACBACCACCBDEDE';
console.log(pickClassPresident(str));

📌 개선사항
1) 루프구조

• 기존 코드에서는 while 루프문을 사용해서 문자열을 순회하지만 코드의 가독성이 떨어질 수 있다.
• for...of 루프를 사용함으로써 JS에서 문자(혹은 배열)의 각 요소를 순회하는 더 일반적이고 간결한 방법으로 개선한다.

2) 최댓값 찾기 - 가독성과 유지보수

• 기존 코드에서는 for...in 루프로 객체의 각 속성을 순회하고 조건문을 사용해서 결과를 구한다. 이것은 최댓값을 찾기 위해 별도의 루프와 조건문이 필요하다.
• 개선된 코드에서는 Object.entries() 와 reduce() 함수를 사용하여 최대 투표 수를 받은 문자를 찾는다. 이 방법은 더 함수형 프로그래밍 접근 방식을 사용하며, 코드를 더 간결하고 선언적으로 만든다.🧐 게다가 reduce() 함수는 최대값을 찾는 로직을 한 줄의 코드로 요약하여 코드의 간결성과 가독성을 높인다.

✍️ solution

function solution(s) {
  let answer;
  let sH = new Map();
  for (let x of s) {
    if (sH.has(x)) sH.set(x, sH.get(x) + 1);
    else sH.set(x, 1);
  }
  let max = Number.MIN_SAFE_INTEGER;
  for (let [key, val] of sH) {
    if (val > max) {
      max = val;
      answer = key;
    }
  }
  return answer;
}

let str = 'BACBACCACCBDEDE';
console.log(solution(str));