[프로그래머스]Hash_완주하지 못한 선수(JS/Level 1)

오늘은 해시를 주제로 푼 두개의 문제를 리뷰하면서 해시(hash)개념을 함께 정리해보려고 한다.

hash

hash는 key와 value를 가지는 자료구조 형태이다.

hash는 배열로 미리 Hash Table 크기만큼 생성해서 사용한다. 공간은 많이 사용하지만 key를 이용하여 데이터를 찾기 때문에 속도를 빠르게 만드는 특징을 가지고 있다.

JS에서 hash를 풀이하는 방법으로 Map을 사용할 수 있다.

new Map() : Map 객체를 만들때 쓰인다.
map.set(key, value) : key를 이용해 value값을 저장한다.
map.get(key) : key에 해당하는 value를 반환한다.

---

- 완주하지 못한 선수

문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.참가자 중에는 동명이인이 있을 수 있습니다.

요약하면 마라톤 경기에 참여한 선수 중 완주하지 못한 선수를 찾아 return 해주면 된다.

나는 이 문제를 보고 두개의 배열을 정렬한 뒤 두 배열의 값을 비교해서 구하면 될 것이라고 생각해 아래와 같이 구현했다.

function solution(participant, completion) {

    participant.sort()
    completion.sort()
    var answer = '';

    for(let i = 0; i<participant.length; i++){
        if(participant[i] !== completion[i]) {
             answer = participant[i];
            break;
    }}
    return answer;
}

하지만 이 문제의 주제는 hash.
hash를 이용하여 이 문제를 풀이하자면 아래와 같다.

function solution(participant, completion) {

 const map = new Map();
    for(let i = 0; i<participant.length; i++){
        let p=participant[i];
        let c=completion[i];

        map.set(p,(map.get(p) ? map.get(p) : 0) +1)
        map.set(c,(map.get(c) ? map.get(c) : 0) -1)

    }
    for(let [key,value] of map){
        if(value > 0) return key
    }
}

참가자 이름을 key로, 1을 더해주는 value로 참가자들을 map 객체에 저장한다.
그 뒤 완주자 명단에 이름이 있다면 -1을 해줘 0을 만들어주고, 완주자 명단에 이름이 없다면 그대로 1이 남아있게 된다.
동명이인이 있을 수 있다. 동명이인의 경우 map객체에 저장할 때 이미 key로 들어가 있는 이름이 있기 때문에 1에서 1을 한번 더 더하게 된다.

완주하지 못한 참가자를 리턴하는 것이기 때문에 0이 되지 못한 참가자가 완주하지 못한 참가자가 된다.

---

아직 개념이 익숙하지 않아 처음 풀이할 때는 배열의 값들을 비교하는 단순한 방식으로 접근했으나, 해시의 방법으로 풀이하니 효율성 테스트에서 훨씬 높은 점수를 받을 수 있었다.