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

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

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

 

입출력 예

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

 

문제 요약

 

• 참가자 배열(participant)과 완주자 배열(completion)을 비교하여 완주하지 못한 단 1명을 찾는 문제.
• 핵심 포인트 1 (동명이인): 참가자 중 이름이 같은 사람이 존재할 수 있으므로 단순한 존재 여부만으로는 판별할 수 없음.
• 핵심 포인트 2 (효율성): 최대 10만 명의 데이터가 주어지므로, 시간 복잡도가 O(n^2)인 배열 탐색 메서드(indexOf 등)를 사용하면 효율성 테스트를 통과할 수 없음.

 

해결방법

최대 10만 명의 참가자 데이터를 효율적으로 처리하고, 가장 까다로운 조건인 '동명이인'을 해결하기 위해 자바스크립트의 Map 객체를 도입했습니다.

 

 

1.  왜 배열 대신 Map을 써야 할까?

• 압도적인 검색 속도 O(1): 배열의 indexOf나 includes는 값을 찾기 위해 배열을 처음부터 끝까지 훑어야 합니다 O(n). 하지만 해시 구조인 Map은 이름(Key)을 통해 값(Value)에 즉시 접근할 수 있어 탐색 시간이 O(1)로 단축됩니다.
• 동명이인 카운팅: 일반적인 단순 존재 여부가 아니라, "이 이름이 몇 번 등장했는가?"를 숫자로 기록할 수 있습니다. 이를 통해 동명이인이 2명, 3명이어도 완벽하게 걸러낼 수 있습니다.

 

2. 핵심 로직: 참가자 명단 기록하기

Map을 활용한 전체 코드 중, 가장 핵심이 되는 한 줄은 바로 참가자를 기록하는 부분입니다.

const pMap = new Map();

participant.forEach(name => {
    // 핵심 코드
    pMap.set(name, (pMap.get(name) || 0) + 1);
});

 

 

코드 동작 원리 파헤치기

1. pMap.get(name) : 먼저 장부(Map)에서 현재 참가자의 이름이 있는지 확인합니다.
2.  || 0 : 논리 연산자(OR)의 단축 평가를 활용한 부분입니다. 장부에 이름이 없어서 undefined가 반환된다면, 기본값으로 0을 할당합니다. (즉, 처음 등장한 이름은 0이 됩니다.)
3. + 1 및 set() : 찾아낸 값 또는 0에 1을 더한 뒤, 다시 pMap.set()을 통해 장부에 최신화된 숫자를 기록합니다.

 

결과적으로 이 로직을 거치면 pMap에는 {'leo' => 1, 'kiki' => 2, 'eden' => 1} 처럼 이름과 해당 이름의 등장 횟수가 깔끔하게 맵핑됩니다. 동명이인인 'kiki'가 2명이라는 것도 정확하게 카운트된 것을 볼 수 있습니다.

이후 완주자 배열(completion)을 순회하며 이 카운트를 -1씩 차감해 주면, 최종적으로 카운트가 1로 남아있는 단 한 사람이 바로 '완주하지 못한 선수'가 됩니다.

 

 

전체 코드

function solution(participant, completion) {
    const pMap = new Map();

    //참가자 명단 카운트하기
    participant.forEach(name => {
        pMap.set(name, (pMap.get(name) || 0) + 1);
    });

    //완주자 명단에서 차감하기
    completion.forEach(name => {
        pMap.set(name, pMap.get(name) - 1);
    });

    //남은 카운트가 1인 사람 찾기
    for (let [name, count] of pMap) {
        if (count > 0) return name;
    }
}