[해시] 학급 회장

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

학급 회장 후보로 기호 A, B, C, D, E 후보가 등록했다.

학급 회장 투표는 학생들이 각 후보의 기호를 적어 내는 것으로 이루어진다.

이때 투표 결과가 발표되면 어떤 후보가 학급 회장으로 선출되었는지를 구하고 학급 회장의 기호를 출력한다.

 

 

👉 입력

첫 번째 줄에 반 학생 수 N이 주어진다.

두 번째 줄에 N개의 투표 용지에 쓰인 각 후보의 기호가 문자열로 주어진다.

이때 주어진 문자열은 문자 사이의 기호나 공백이 없다.

 

 

👈 출력

학급 회장으로 뽑힌 후보의 기호를 출력한다.

 

 

💡 사용된 개념

Hash

다양한 길이를 가진 데이터(key)를 고정된 길이를 가진 데이터로 매핑한 값이다.

 

key를 매우 큰 값이라 가정했을 때 이 값을 자료구조에 저장하기 위해서는 축소시키는 과정이 필요하다.

이때 key를 저장할 자료구조의 index를 지정하는 방식이 해시 함수(hash function)을 통해 이루어진다.

 

해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말하며 이때 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다.

즉, 임의의 해시 함수를 통해 key값을 작은 값으로 변환 후 그 인덱스 값에 data를 삽입한다.

이러한 방식으로 data를 저장하거나 찾는 것이 가능해진다.

 

hashing은 ‘단번에 찾는다’가 목표이다. 이는 이상적인 상황에서는 가능하다.

그러나 2개의 다른 key가 하나의 동일한 index와 매핑될 때 충돌(Collision)이 발생할 가능성이 존재한다. 

 

hashing 예시

 

 

Map

Map object는 key-value 쌍을 저장하는 객체이다.

이때 key가 삽입된 순서대로 저장된다.

 

어떠한 key, value 값이 저장된 Map 객체가 존재한다고 했을 때 이 Map 객체 안에 저장된 key와 value를 참조하는 것은 다음과 같다.

 

// 어떠한 key-value 값이 저장된 Map 객체 map이 있다고 가정.

for(const [key, value] of map){
    // ...
}

for(const key of map.keys()){
    // ...
}

for(const value of map.values()){
    // ...
}

 

 

Map.set()

set(key, value)

set 함수를 통해 Map에 key와 value를 저장할 수 있다.

 

Map.get()

get(key)

get 함수를 통해 주어진 key 값에 해당하는 value 값을 얻을 수 있다.

 

Map.has()

has(key)

has 함수를 통해 주어진 key 값에 해당하는 key가 있는지 확인할 수 있다.

동일한 key가 있다면 true, 없다면 false가 리턴된다.

 

Map.delete()

delete(key)

delete 함수를 통해 주어진 key 값에 해당하는 key - value 쌍을 Map에서 삭제한다.

주어진 key값이 Map에 있어 해당 값이 삭제되었다면 true, 삭제하지 못했다면 false를 리턴한다.

 

 

📝 풀이

 

function solution(s) {
    let answer;
    let max = Number.MIN_SAFE_INTEGER;
    let map = new Map();

    for (const i of s) {
        if (map.has(i)) map.set(i, map.get(i) + 1);
        else map.set(i, 1);
    }

    for (const [key, value] of map) {
        if (value > max) {
            max = value;
            answer = key;
        }
    }

    return answer;
}

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

 

최댓값을 저장할 변수인 max에 최소 정수값을 저장하고 map에 Map 객체를 만든다.

 

주어진 문자열 s의 각 후보의 기호들을 하나씩 순회하며 map에 담는다.

이때 map에 해당 기호(key)가 이미 있다면 해당 기호가 등장한 수(value)에 1을 더한다.

map에 해당 기호(key)가 없다면 처음 등장한 것이기 때문에 기호를 key로, 등장한 횟수(1)를 value로 하여 map에 이 key-value 쌍을 저장한다.

 

문자열의 순회가 끝나면 map에는 각 후보 - 각 후보의 득표 수 쌍이 저장되어있다.

map의 key와 value를 순회하며 value의 값이 제일 큰 것을 찾아낸 후 answer에 value가 제일 큰 값을 가진 key를 저장한다.