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

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

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

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

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

Solution

처음에는 participant 의 아이템 하나 하나씩이 completion 배열에 item으로 있는지 검사 해볼까 생각했다.
그러나 이 방법은 최대 participant, completion 의 곱인 100,000 명 X 99,999 명 의 시간복잡도를 가질 수 있어서 오래 걸린다.
Object 를 만들어 participant, completion 배열을 각각 따로 따로 for 문을 돌아보면 어떨까 생각해봤다.
초기 빈 Object 를 만들어 participant 의 이름대로 Object의 키를 만들고 value로 false 를 넣어줬다. completion 을 for 문을 타면서 Object 의 있는 key들의 value를 하나씩 true 로 바꿔 대입해주기 위해서다. (true 로 바뀐 key 들은 완주를 했다는 말)
그러나 또 이 방법은 동명이인이 나왔을 때 문제가 된다. 앞에서 이미 true로 바꿔준 key들로 인해 완주하지 못한 선수가 제대로 리턴이 안되는 문제가...
그래서 결론은, false/true 대신 숫자를 넣어주는 방법을 생각했다.
participant 배열의 참가자들은 Object에서 value 1을 갖는 key 를 가져 Object에 들어가고 동명이인이라면 2가 된다.
마지막에 completion 배열을 돌며 숫자들을 -1 해주는데 value가 1인 key는 완주하지 못한 선수로 보고 해당 아이템을 반환한다.

function solution(participant, completion) {
    const completed = {}
    
    participant.forEach(key => {
        if (completed.hasOwnProperty(key)) {
            return completed[key] += 1
        }
        
        return completed[key] = 1
    })
    
    completion.forEach(key => {
        completed[key] -= 1
    })
    
    const result = Object.keys(completed).filter(key => completed[key] === 1)
    return result.toString()
}