[프로그래머스] 완주하지 못한 선수 JS 풀이

1. 문제설명

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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"
---------------------------------------------------------------------------------------------------------

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

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

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

2. 나의 풀이

2-1) 문제 정의와 나의 풀이

<문제 정의>

1. 참가자(participant) 수만큼 반복해서 참가자의 이름을 등록하고 등록된 횟수를 저장한다. (동명이인인 경우 같은 이름으로 등록된 횟수를 하나더 올린다.)
2. 완주자(completion) 수만큼 반복해서 참가자로 등록된 횟수를 1만큼 감소시킨다.
3. 최종 등록된 참가자의 수가 1인 이름을 retur한다.

function solution(participant, completion) {
    // key-value 형태로 저장이 가능한 Map객체 생성
    const map = new Map();
    // 참가자 수만큼 반복해서 map 객체 중 key에는 참가자 이름을, value에는 같은 이름으로 등록된 참가자의 수를 등록한다.
    for(let i=0; i<participant.length; i++){
        map.set(participant[i], map.get(participant[i]) ? map.get(participant[i]) + 1 : 1)
    }
    // 완주자 수만큼 반복해서 같은 이름으로 등록된 참가자 value의 값을 1씩 감소시킨다.
    for(let i=0; i<completion.length; i++){
        map.set(completion[i], map.get(completion[i]) - 1)
    }
    // 같은 이름으로 등록된 참가자의 value가 1인 값을 찾아 return한다.
    return [...map].filter(v=>v[1]===1)[0][0]
}

2-2) 나의 풀이 채점결과

3. 다른 사람의 풀이

3-1) 다른 사람의 풀이

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

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

3-2) 다른 사람의 풀이 채점 결과

4. 느낀 점

<나의 풀이와 달랐던 점과 배운 점>

• 다른 사람에 풀이 접근법은 참가자와 완주자를 이름순으로 정렬했을 때, 처음 달라지는 이름을 찾는 방법이다.(접근법이 참신했다.)
• 하지만 효용성 테스트에서는 나의 풀이가 훨씬 빠르게 계산한다. 나의 예상이지만 자바스크립트의 해시맵 구조인 Map에서 자료에 접근하는 시간복잡도가 O(1)인 방법을 두 번의 반복문 안에서 이용하였고, filter 메서드(O(n))를 이용했기 때문에 총 3n의 시간복잡도(정확히는 3n-2로 예상되지만 상수는 버림)가 예상된다면, 다른 사람의 풀이는 두 번의 sort 메서드를 통해 2nlog(n), 그리고 반복문을 통해 O(n)을 더하여 총 2nlog(n)+n의 시간복잡도가 예상된다. 따라서, 참가자의 수가 10명 이상부터는 다른 사람의 풀이가 비효율적으로 보인다.
• 해시는 배열 안에 같은 요소가 존재할 때, 같은 값의 요소가 몇 개가 존재하는지 확인하고 수정하기에 용이하다.