완주하지 못한 선수

Problem

마라톤에 참여한 선수들의 이름이 담긴 배열과 완주한 선수들의 이름이 담긴 배열이 주어질 때, 완주하지 못한 선수의 이름을 return하는 함수 구현

Algorithm

해시 : Key-Value 형태로 데이터를 저장하기에 검색과 저장이 빠르게 일어나는 Javascript의 일반 객체 또는 Map을 적용하여 문제를 해결하는 알고리즘

Solution 1

1. 마라톤 참여자와 완주자 리스트를 둘 다 정렬
2. 처음부터 인덱스로 순회
3. 만약 똑같은 인덱스인데 서로 다른 이름을 가리킬 시 이는 해당 이름을 가진 참여자가 완주를 하지 못한 것이기에 해당 참여자 이름을 반환

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

Solution 2

해시 알고리즘에 적합한 Map 객체를 이용한 문제 풀이 방법

1. key는 해당 참가자/완주자 이름, value는 이름 조회 회수인 Map 객체 선언
2. 참가자와 완주자를 전체 순회하면서 참가자 이름 조회시 회수 1 증가, 완주자 이름 조회시 회수 1 감소로 세팅
3. 만약 map을 순회했을 때, value가 0을 초과한다면, 이는 참가자 이름으로 조회됬지만, 완주자 이름에 없다는 뜻이기에 해당 이름 반환

function solution(participant, completion) {
    const map = new Map();
    for (let i = 0; i < participant.length; i++) {
        let a = participant[i], b = completion[i];
        map.set(a, (map.get(a) || 0) + 1); 
        map.set(b, (map.get(b) || 0) - 1);
    }
    for (let [k, v] of map) {
        if(v > 0) return k;
    }
    return 'nothing';
}