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

2021_11_14 알고리즘 스터디 문제 풀이

 

문제 URL 

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

문제

마라톤에 참가했지만 완주는 못한 1인의 이름을 출력하는 문제이며, 이 문제에서 신경써야할 부분은 동명이인이 있을 수 있다는 점이다.

문제를 보자마자 두 가지의 문제 풀이가 떠올랐다.

• completion을 순회하면서 그 요소로 participant에서 해당되는 인덱스를 찾고, slice한 값을  participant에 계속 재할당, 최종적으로 남은 참가자를 리턴하는 방법 (O(n^2))
• participant를 순회하면서 빈객체에 Key를 부여하고 값은 등장 횟수마다 1씩 증가
  completion을 순회하면서 객체에 key로 값을 찾아 -1씩 감소시킨다
  객체를 순회하면서, 값이 0이 아닌 것의 이름을 찾아 리턴한다 (O(n)) -> 특정 이름의 참가자 횟수를 카운팅하고, 완주했을 경우 1씩 감소 시키는 것, 만약 객체에서 0이 아닌 값을 갖고 있는 키가 있다면, 완주하지 못한 것 

시간 복잡도를 고려하여 2의 방법으로 구현했다

 

풀이

function solution(participant, completion) {
    let obj = {};
    
    for (let el of participant) {
        if (obj[el]) {
            obj[el] += 1;
        } else {
            obj[el] = 1;
        }
    }
    for (let el of completion) {
        obj[el] -= 1; 
    }
    for (let key in obj) {
        if (obj[key] !== 0) return key;
    }
}