알고리즘 문제풀이📝 Hash(1)

프로그래머스 완주하지 못한 선수

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

🌙 방법 1(시간 초과)

completion배열 돌면서 participant배열에 해당 값의 인덱스 찾아 제거

function solution(participant, completion) {

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

🌙 방법 2

동일하게 정렬 사용
정렬했는데 틀린 경우에 바로 return

function solution(participant, completion) {
  
    participant.sort();
    completion.sort();
    
    
    for(let i=0;i<participant.length;i++){
        if(participant[i] !== completion[i]){
            return participant[i];
        }
    }
}
테스트 1 〉	통과 (44.07ms, 41.3MB)
테스트 2 〉	통과 (79.85ms, 47.8MB)
테스트 3 〉	통과 (96.37ms, 52.4MB)
테스트 4 〉	통과 (104.29ms, 55.1MB)
테스트 5 〉	통과 (110.10ms, 53.6MB)

🌙 방법 3

해당 정보를 hash로 구현한다
해당하는 key가 나오면 value를 하나씩 낮춰준다
value값으로 해당 key값을 찾으려면 for문을 전부 돌려야한다

function solution(participant, completion) {
    const hash = {};
    
   
    for(let p of participant) {
      if(!hash[p]){hash[p] = 1;
      }else{
      hash[p] +=1;}
    }
    
    completion.forEach(p => hash[p]-=1);
    
    for(let key in hash){
        if(hash[key]) {
            return key;
        }
    }  
}

테스트 1 〉	통과 (35.21ms, 48.4MB)
테스트 2 〉	통과 (51.07ms, 53.3MB)
테스트 3 〉	통과 (60.76ms, 57MB)
테스트 4 〉	통과 (66.19ms, 65.7MB)
테스트 5 〉	통과 (87.14ms, 65.4MB)

이 문제는 Hash를 사용했을 때 더 효율적인 풀이가 된다