[js] - 완주하지 못한 선수 (Hash)

1. 해시(Map)를 이용한 방법

Map 객체를 사용하여 각 이름의 등장 횟수를 기록한다.

[동작 원리]

• participant를 돌며 이름이 나올 때마다 +1을 한다.
• completion을 돌며 완주한 이름이 나올 때마다 -1을 한다.
• 최종적으로 값이 1인 사람이 완주하지 못한 선수이다.

[Map의 핵심 함수]

• new Map(): JavaScript에서 해시 테이블(Hash Table) 자료구조를 구현하기 위해 사용하는 가장 대표적인 방법
• map.get(key): 특정 키에 저장된 값을 가져옵니다. (없으면 undefined)
• map.set(key, value): 특정 키에 값을 저장하거나 업데이트합니다. (이미 키가 존재하면 기존 값을 덮어씀)
• map.has(key): 특정 키가 존재하는지 여부를 boolean으로 반환합니다.
• map.delete(key): 특정 키와 그 값을 삭제합니다.
• map.clear: 모든 데이터를 지웁니다.

왜 Map을 해시 테이블이라고 부를까요?
일반적인 해시 테이블의 동작 원리를 Map의 문법과 연결해 보면 이해가 쉽습니다.

• Key(키): 우리가 map.set(key, value)에서 사용하는 '키'입니다.
• Hash Function(해시 함수): JavaScript 엔진이 내부적으로 키를 해시값으로 변환합니다.
• Bucket(저장소): 변환된 해시값을 인덱스로 삼아 값을 특정 공간에 저장합니다.

Map의 이점

• 키의 타입에 제한이 없음 (객체는 문자열만 키로 쓸 수 있지만, Map은 무엇이든 키가 될 수 있음)
• 데이터 개수 확인이 매우 쉬움 (console.log(myMap.size); // 데이터 개수 출력)
• 삽입 순서 보장 (해시 테이블은 보통 순서를 보장하지 않는 경우가 많지만, JavaScript의 Map은 데이터가 들어온 순서대로 정렬되어 있어 순회(Iteration)할 때 편리함)

정답

function solution(participant, completion) {
    const marathonMap = new Map(); // 빈 테이블 생성 [name, count]
    
    // 1) 참여자 명단을 Map에 기록 (동명이인 고려)
    for (const name of participant) {
        marathonMap.set(name, (marathonMap.get(name) || 0) + 1);
    }
    
    // 2) 완주자 지우기
    for (const name of completion) {
        marathonMap.set(name, marathonMap.get(name) -1);
    }
    
    // 3) 남은 값이 1인 사람(완주 못한 사람) 찾기
    for (const [name, count] of marathonMap) { // for...of + 구조분해할당
        if (count > 0) return name;
    }
}

만약 완주하지 못한 사람이 여러명이라면?

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

    // 1. 참여자 카운트업
    for (const name of participant) {
        marathonMap.set(name, (marathonMap.get(name) || 0) + 1);
    }

    // 2. 완주자 카운트다운
    for (const name of completion) {
        marathonMap.set(name, marathonMap.get(name) - 1);
    }

    // 3. 결과 담을 배열 생성 (여러 명이니까!)
    const result = [];
    for (const [name, count] of marathonMap) {
        // 0보다 크다면 그 값(인원수)만큼 배열에 추가
        if (count > 0) {
            for (let i = 0; i < count; i++) {
                result.push(name);
            }
        }
    }
    return result; // 미완주자 이름들이 담긴 배열 반환
}

2. 정렬(Sorting)을 이용한 방법

직관적이고 코드가 깔끔하지만, 정렬 알고리즘의 시간 복잡도($O(n \log n)$)를 가진다.

[동작 원리]

• 두 배열을 가나다순으로 정렬합니다.
• 인덱스 0부터 차례대로 비교합니다.
• 서로 이름이 다른 지점이 생기면, 그 participant의 해당 인덱스 선수가 바로 완주하지 못한 사람입니다.

왜 정렬을 해야 할까?
원래 participant와 completion 배열은 이름이 들어있는 순서가 제멋대로입니다. 순서가 다르면 하나하나 찾아서 비교해야 하므로 시간이 오래 걸리게 됩니다.

하지만 두 배열을 똑같이 가나다순(알파벳순)으로 정렬하면, 완주한 사람들은 두 배열에서 정확히 같은 인덱스(위치)에 놓이게 됩니다.

participant.sort(); // ["ana", "mislav", "mislav", "stanko"]
completion.sort();  // ["ana", "mislav", "stanko"]

정답

function solution(participant, completion) {
    // 1. 두 배열을 정렬한다.
    participant.sort();
    completion.sort();

    // 2. 인덱스를 돌며 서로 다른 값을 찾는다.
    for (let i = 0; i < participant.length; i++) {
        if (participant[i] !== completion[i]) {
            return participant[i];
        }
    }
}