프로그래머스 Lv.1 | 완주하지 못한 선수 js

문제

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

 

풀이

통과한 풀이

1. 두 배열을 정렬한다.
2. completion을 돌며 completion[i]가 participant[i]와 어긋나기 시작한 최초의 지점이 바로 완주하지 못한 참가자가 위치한 곳이므로 그 참가자를 반환한다.
3. completion을 다 돌아도 어긋난 지점을 찾지 못한다면 participant의 마지막에 위치한 참가자가 완주 못한 것이므로 그 사람을 반환한다.

 

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

 

맨 처음에 풀었지만 효율성을 통과 못한 풀이

1. completion을 돌며 해당 요소가 participant에 존재하는지 indexOf로 검사, 있다면 participant에서 제거하기
2. 최후에 남는 요소를 반환

테스트 케이스는 통과했지만 효율성 검사에서 통과 못해서 위의 풀이로 다시 풀었다.

completion.forEach(c => {
    const index = participant.indexOf(c);
    participant.splice(index, 1);
});
return participant[0];

 

Hash 방식으로 푼다면

문제 유형이 Hash이므로 취지에 맞게 Map object를 이용해 푼다면 빈도수를 세는 문제와 비슷하게 접근할 수 있다.

1. participant를 돌면서 Map에 참가자 이름: value를 추가한다. map.has()로 검사해 동명이인이 있는지 검사하고, 없다면 새 값을 1로 등록, 존재한다면 map.get(참가자) + 1로 사람을 증가시킨다.
2. completion을 돌면서 participant Map에 해당 이름을 가진 사람의 수를 Map.get()으로 검사해서, 1이라면 그 사람의 이름을 Map에서 delete하고, 1이 아니라면 value를 -1 한다.
3. 최후에 Map에 남아있는 사람의 이름을 반환한다.

참고로 Map.values()로 value들을 담은 배열을 얻을 수 있는 것과는 다르게 Map.keys()는 key를 순회할 수 있는 iterator를 반환한다.

따라서 이런 식으로 직접 key를 담은 배열을 구해야 한다.

const result = [];
for (const key of myMap.keys()) {
    result.push(key);
}