[Programmers / JS] 42576번 - 완주하지 못한 선수

Problem

문제 보기

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.

---

Solution

문제분석
completion의 길이는 participant의 길이보다 1 작음 -> 즉, 1명만 return하면 됨
동명이인이 있을 수 있음
return 마라톤 완주하지 못한 선수 이름

문제풀이
1. 정렬하면 두 매개변수가 같은 차례대로 있게 된다
2. 차례대로 두 매개변수를 비교해준다.

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

위의 sort메서드를 이용해서 통과를 했으나
이 문제는 해시라는 특징을 이용하여 논리적으로 풀어야한다.

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';
}

다른 코드를 봤을 때 위의 코드가 해시를 이용하여 가독성 있게 풀어냈다.

1. map.set메서드로 map에 새로운 객체를 추가한다
2. map.set(key, value)형태로 객체를 추가하게 된다
3. key값으로 a가 전달되고  value값으로 ( map.get(a) || 0 ) + 1 이 전달되는데 a가 처음 추가되는 상황이라면 map.get(a)가 false이므로 0이 출력값으로 되고 1을 더하므로 결과적으로 value에는 1이 전달된다.
4. map에 a가 이미 추가되어있는 상황이라면 (동명이인) map.get(a)가 true이므로 map.get(a)가 출력값으로 되는데 즉 1이 나오게 된다. 여기에 1을 더하므로 결과적으로 value에는 2가 전달된다
5. a가 끝나고 b를 보면 value값을 가져오고 같은 값이 있다면 -1을 하게 된다.
6. for문으로 각 value값이 0이상인 즉 1인(미완주자) 값이 출력하게 된다.

const solution = (p, c) => {
    p.sort()
    c.sort()
    while (p.length) {
        let pp = p.pop()
        if (pp !== c.pop()) return pp
    }
}

위 코드는 해시를 이용한 것은 아니지만 나와 같은 sort정렬을 사용했지만 sort를 이용하여 생각하지 못한 코드를 작성하여 인상 깊어 가져왔다. 특히 while (p.length)로 0이 false되는 것을 이용하여 반복문을 사용한 것이 좋았다.