JavaScript 해시 완주하지 못한 선수

프로그래머스 완주하지 못한 선수 자바스크립트 풀이

실패한 풀이1, 2

function solution(participant, completion) {
    for (let i = 0; i < completion.length; i++){
       const n = participant.indexOf(completion[i])
       participant.splice(n, 1);
    };
    const answer = participant[0];
    return answer;
}

function solution(participant, completion) {
    let i = 0;
    while (participant.includes(completion[i])){
        const n = participant.indexOf(completion[i]);
        participant.splice(n, 1);
        i++;
    };
    const answer = participant[0];
    return answer;
}

 

해시는 키로 값을 찾는 자료구조라고 알고있는데 해당 문제에서 해시를 활용하려 푸는 방법이 떠오르지 않았습니다. 예상대로 시간 초과로 효율성 테스트 부분에서 실패하였습니다.

 

제한사항을 확인하니 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.라고 하였네요.

 

10만 이하라면 요구 시간 복잡도는 O(N)이하 알고리즘이어야겠군요. 실패한 코드의 시간 복잡도는 O(N**2)입니다.

간단하게 해시를 사용하지않고 정렬 비교로 시간복잡도만 고려해서 푸는 방법은 아래와 같습니다.

function solution(participant, completion) {
    participant.sort();
    completion.sort();
    for(let i = 0; i < participant.length; i++){
        if (participant[i] !== completion[i]) return participant[i];
    }
}

해시 사용해서 풀어보기

해시로 처음 푼다고 생각했을 때는 participant,completion값을 키로 반환하여 비교하여 제거하는 방법을 생각했습니다.

제한사항을 제대로 고려하지 않고 푼 코드

function solutionNoDup(participant, completion) {
  const s = new Set(participant);
  for (const name of completion) {
    s.delete(name);
  }
  return s.values().next().value;
}

 

제한사항을 제대로 안읽고 풀면 이렇게 실수를 하네요. 동명이인이 있다는 점을 고려하면 participant에서 같은 이름이 나올 때마다 +1 더해 저장하고 completion 명단에서 이름이 나오면 -1을 하는 로직이 필요합니다. 최종적으로 나온 solution코드는 아래와 같습니다.

function solution(participant, completion) {
    const  countMap = new Map();

    for ( const name of participant ){
        countMap.set(name, (countMap.get(name) || 0) + 1);
    };

    for ( const name of completion ){
        countMap.set(name, (countMap.get(name) || 0) - 1);
    };

    for (const [name, count] of countMap){
        if( v > 0 ) return k;
    };
    return;
}

해시를 활용한 이유

왜 우리는 해시를 써야할까요?

해시는 키(key)를 통해 빠르게 조회, 저장할 수 있는 자료구조로 JavaScript에서는 Map이나 일반 객체({})로 구현할 수 있습니다.

 

자바스크립트의 new Map()에서는 set으로 중복값 없이 key값을 등록할 수 있는데, 이때 동명이인을 처리할 때 이름의 등장 횟수를 particiant에서 등장하면 +1, completion에 등장하면 -1을 통해 완주유무를 확인할 수 있습니다.

마지막 반복문에서는 완주하지 못한 이름은 0이상이 됨으로 값(count)가 0이상인 경우만 반환해주면 정답이 출력됩니다.