[JavaScript] Lv.1 완주하지 못한 선수

문제

수많은 마라톤 선수들이 참가
단 한 명의 선수만 미완주
participant : 참여선수들의 이름이 담긴 배열
completion : 완주한 선수들의 이름 배열

완주하지 못한 선수의 이름을 return

 

문제를 풀려고 30분동안 고민을 했지만, 아직 내 머리로는 풀리지가 않았음.

 

그래서 아래 코드를 구글링으로 가져와서 그냥 풀어버리고 외워 버렸다.

function solution(participant, completion) {
    participant.sort();
    completion.sort();

    for(let i in participant) {
        if(participant[i] !== completion[i]) return participant[i];
    }
}

---

초보자들이 문제를 풀때 위와 같은 코드를 많이 쓸 것이라고 생각한다.

 

코드의 원리는 p와 c의 그룹을 정렬시켜서 푸는 것이다.

 

위 코드의 문제점이 있다고 생각한다.

 

1. sort 함수를 사용했기 때문에 정렬이 되었고, 인덱스 0 부터 비교를 시작한다.

해당 문제의 경우 완주하지 못한 사람이 1명이 아니였다면? 어땟을까?

완주하지 못한 사람 한명을 찾아내고 for문은 진행을 멈출 것이다.

 

2. 만약 참여선수와 완주한 선수의 명단이 엄청나게 커질경우

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

map.set 메소드로
map에 새로운 객체를 추가

map.set(key, value)형태로 객체를 추가
a, 즉 participant의 첫 요소부터 추가
key값으로 a가 전달
value 값으로 map.get(a) || 0 + 1    이 전달
a가 처음 추가되는 상황이므로 map.get(a)가 false 이므로 0이 출력
1을 더하니 결과적으로 key에 a, value에 1이 map에 저장

만약
map에 a가 이미 추가되어 있는 상황이라면(동명이인) map에 key가 value가 1인 객체
가 있는 상황임.
그렇게 되면 map.get(a)가 true가 되므로 map.get(a) || 0 가 map.get(a)가 나오게 되고
(즉 1이 나오게 됨) +1을 하면 a의 value값으로 2가 전달 되는 것임.

b를 살펴보면 같은 원리로 b가 이미 map에 있다면(즉 완주자라면)a 1 인상태에서
-1이 되어 value 값이 0이 된다.

반대로 없는 경우에는(미완주자) a에서 는 있었으므로 value 값이 1이지만 완주를 못해 b에서는
없으므로 아무변화가 없어 value값이 1인 상태로 남게 됨.

또한 동명이인의 경우에는 a에서 한번 더 1이 더해져 value가 2인 상태에서 b에서 1을 
뺀다고 해도 값이 1이 남게 됨.
결국 아래 for문에서 value값이 0이상 즉 1인 값들(미완주자, 동명이인)이 출력 되게됨.

---

function solution(participant, completion) {
    var dic = completion.reduce((obj, t)=> (obj[t]= obj[t] ? obj[t]+1 : 1 , obj) ,{});
    return participant.find(t=> {
        if(dic[t])
            dic[t] = dic[t]-1;
        else 
            return true;
    });
}

공부예정(22/06/27)

백엔드 공부 + 지식부족으로 이해하기 어려움