[프로그래머스 Level 1] 완주하지 못한 선수 - JavaScript

문제 링크

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

코딩테스트 연습 - 완주하지 못한 선수

풀이

function solution(participant, completion) {
    const map = new Map();
    participant.forEach(name => map.set(name, (map.get(name) || 0) + 1));
    completion.forEach(name => map.set(name, (map.get(name) || 0) - 1));
    for (const [name, value] of map) {
        if (value) {
            return name;
        }
    }
}

참가자 배열을 순회하면서 이름이 나온 횟수를 map에 저장한다.

그리고 나서 완주자 배열을 순회하면서 이름이 나온 횟수만큼 map의 value에서 뺀다.

그렇게 하면 최종적으로 완주하지 못한 선수의 이름의 value는 1이고 나머지 이름은 모두 0이 된다.

map을 순회하면서 value가 1인 값의 key(이름)를 출력하였다.

 

이 문제는 sort로도 해결할 수 있지만 sort를 사용하면 O(NlogN) 시간이 걸리는 반면,

해시(Map)로 풀면 O(N) 시간이 걸린다.