[JS] 프로그래머스 코딩테스트 연습 | 해시 - 완주하지 못한 선수

문제링크 : 해시 > 완주하지 못한 선수

1. 문제

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

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

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

2. 입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

---

3. 내 풀이

function solution(participant, completion) {
  const table = new Map();
// 참가자 ++1
  for (let i = 0; i < participant.length; i++) {
    table.has(participant[i])
      ? table.set(participant[i], table.get(participant[i]) + 1)
      : table.set(participant[i], 1);
  }
  // 도착한 참가자 -- 1
  for (let j = 0; j < completion.length; j++) {
      table.set(completion[j], table.get(completion[j]) - 1);
  }

  for (let [key, val] of table) {
    if (val > 0) return key;
  }

  return;
}

1. 먼저 해시 문제를 풀어야하니까 table이라는 이름의 map을 만들어준다
2. 다음으로 참가자의 이름을 key, 이름의 개수를 value로 넣어준다
3. 완주한 사람의 이름(key)의 value 값에서 -1을 해준다
4. 마지막으로 val값이 0 이상 즉 완주한 사람보다 참가자가 많을 경우 이름을 반환하고 모두 도착했다면 그냥 return한다

   

---

4. 다른 사람의 풀이

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을 이용해서 푼 풀이 근데 이게 더 효율적이다.
1. 먼저 map을 만들어준다
2. 참가자는 a, 완주자는 b라고 할 때 a 키에는 기존값이 있다면 거기에+1 없다면 0 +1을 b키도 마찬가지로 기존 값이 있다면 거기에 -1을 없다면 0에 -1을 해준다(이렇게 만들면 has를 사용하지 않아도 된다!)
3. 마지막으로 val값이 0 이상 즉 완주한 사람보다 참가자가 많을 경우 이름을 반환하고 모두 도착했다면 그냥 return한다

이 코드를 보고나니 어느 부분에서 비효율성이 발생했는지 알 수 있었다.

---

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

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

1. 참가자와 완주자를 오름차순으로 정렬한다
2. 만약 참가자[i]와 완주자[i]가 다르다면 참가자를 반환한다

해시 배우기 전에 푼 코드랑 비슷해서 가져온 풀이이다.
3가지 코드 중에서는 가장 비효율적이다.