PR-완주하지 못한 선수

문제

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

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

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

예시

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"

풀이

• completion에는 있고 participant 에는 없는 하나의 원소를 찾아내는 문제이다.
• while문과 for문을 3~4개쯤 중첩하면 검색 효율성 면에서 빵점을 맞을 수 있다.
• 자료구조 중 데이터 검색에 O(1) 의 시간복잡도를 갖고 있는 Hash Table을 쓰자.
• participant 배열 내 원소를 key로 갖는 객체를 생성한다.
• 객체의 value 는 1로 초기화하고, 동명이인이 나올 때마다 value를 1 씩 더한다.
• 객체의 key 와 completion의 원소를 비교해서, 일치할 때마다 해당 key의 value를 1씩 뺀다.
• 객체 내에서 value가 1 인 원소를 반환한다.

코드

function solution(participant, completion) {
    let runners = {};
    
    participant.forEach((e) => {
        if(runners[e]) {
            runners[e]++;
        } else {
            runners[e] = 1;
        }
    })
    
    for(let i = 0; i < completion.length; i++) {
        runners[completion[i]]--;
    }

    for(let i in runners) {
        if(runners[i] === 1) {
            // console.log(i);
            return i;
        }
    }
}