[해시] 프로그래머스 '완주하지 못한 선수' - js

1. 문제

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

프로그래머스

2. 코드

1. 해시 미사용 풀이법 - sort()

어디서인지는 모르겠지만, 첫번째로 푼 방식에서는 타임아웃이 났다. indexOf 는 모든 요소를 검사해야하기 때문에 시간이 오래걸린다.

이 문제의 핵심은 두 배열을 sort해준 후 비교한다는 것이다. 두 배열을 sort해준  후 같은 인덱스에서의 값이 다르면 참가자 배열의 i번째 인덱스에 해당하는 사람이 마라톤을 완주하지 못한 것이 되고, 이는 참가자에 동명이인이 있더라도 문제없이 작동한다.

정렬 전

참가자 : ["mislav", "stanko", "mislav", "ana"]

완주자: ["stanko", "ana", "mislav"]

정렬 후

참가자 :[ 'ana', 'mislav', 'mislav', 'stanko' ]

완주자: [ 'ana', 'mislav', 'stanko' ]

타임아웃)

function solution(participant, completion) {
    var answer = '';
    let count = 0;
    for(let i=0;i<participant.length;i++){
        if(completion.includes(participant[i])){
            count = completion.indexOf(participant[i])
            completion[count] = '';
        }
        else{
            answer += participant[i];
            break;
        }
    }
   
    
    return answer;
}

정답)

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

 

2. 해시 사용 풀이법

타임아웃 및 부분 정답)

function solution(participant, completion) {
    let map = new Map();
    
    for(let i=0;i<completion.length;i++){
        map.set(completion[i], (map.get(completion[i]) || 0) + 1);
    }
    
    for([key,value] of map){
        participant.splice(participant.indexOf(key),1);
    }
    
    return participant[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;
    }
}