[프로그래머스] JavaScript Lv1 - 완주하지 못한 선수(42576)

개요

문제 이름: 완주하지 못한 선수 (42576)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576
플랫폼: 프로그래머스
알고리즘 분류: 해시
소요 시간: 50분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 마라톤 경기에 참가한 선수들 중 완주하지 못한 한 명의 선수를 찾아내는 알고리즘 문제입니다. 참가자 배열과 완주자 배열이 주어지며, 완주하지 못한 선수의 이름을 반환해야 합니다.

문제를 해결하기 위해 '해시 알고리즘'을 사용할 수 있습니다. 해시 알고리즘은 키(key)와 값(value)을 매핑하여 데이터를 저장하고 검색하는 알고리즘으로, 빠른 검색 속도를 제공합니다. 이 문제에서는 참가자의 이름을 키로, 참가자의 수를 값으로 하는 해시 테이블을 만들어 문제를 해결할 수 있습니다.

JavaScript에서는 Map 객체를 사용하여 해시 테이블을 구현할 수 있습니다. Map은 키-값 쌍을 저장하는 객체로, 다음과 같은 주요 메서드를 제공합니다.

• set(key, value): 주어진 키에 값을 저장합니다. 이미 존재하는 키라면 값이 업데이트됩니다.
• get(key): 주어진 키에 해당하는 값을 반환합니다. 키가 존재하지 않으면 undefined를 반환합니다.
• has(key): 주어진 키가 Map에 존재하는지 여부를 boolean 값으로 반환합니다.
• delete(key): 주어진 키와 그 값을 Map에서 삭제합니다.
• clear(): Map의 모든 키-값 쌍을 삭제합니다.
• size: Map에 저장된 키-값 쌍의 개수를 반환합니다.

 

Map을 사용하여 문제를 해결하는 과정은 다음과 같습니다.

1. 참가자 배열을 순회하면서 해시 테이블에 참가자의 이름과 수를 저장합니다.
2. 이때 동명이인이 있을 수 있으므로 기존에 이름이 존재하면 값을 1 증가시킵니다.
3. 완주자 배열을 순회하면서 Map에서 해당 이름의 값을 1 감소시킵니다.
4. 해시 테이블을 순회하면서 값이 0보다 큰 경우, 즉 완주하지 못한 선수의 이름을 반환합니다.

위 과정을 통해 완주하지 못한 선수의 이름을 효율적으로 찾아낼 수 있습니다.

 

시도

1차 시도  (실패)

// 1차 시도 (실패) - Set 사용
function solution(participant, completion) {
    let participantSet = new Set(participant);
    let completionSet = new Set(completion);
    
    let result = participant.filter((value) => !completionSet.has(value))
    console.log(result);
}

처음에는 Set 자료구조를 사용하여 문제를 해결하려고 했습니다. 참가자 배열과 완주자 배열을 Set으로 변환한 후, 참가자 Set에는 있지만 완주자 Set에는 없는 이름을 필터링하여 결과를 얻으려 했습니다. 그러나 이 방법으로는 동명이인이 있을 경우 정확한 결과를 얻을 수 없어 실패했습니다.

 

2차 시도  (성공)

// 2차 시도 (성공) - 해시 미사용
function solution(participant, completion) {
    participant.sort();
    completion.sort();
    
    for(let i = 0;i<=participant.length;i++) {
        if(participant[i] != completion[i])
            return participant[i];
    }
}

해시를 사용하지 않고 문제를 해결하는 방법으로, 참가자 배열과 완주자 배열을 정렬한 후 같은 인덱스끼리 비교하는 방식을 사용했습니다. 정렬 후 같은 인덱스의 이름이 다른 경우, 해당 이름이 완주하지 못한 선수의 이름이 됩니다. 이 방법은 간단하지만 정렬에 O(nlogn)의 시간 복잡도가 소요됩니다.

 

3차 시도 (성공)

// 3차 시도 (성공) - 해시 사용
function solution(participant, completion) {   
    let hashMap = new Map();
    for(let i = 0;i<=participant.length;i++) {
        let par = participant[i];
        let com = completion[i];
        hashMap.set(par, (hashMap.get(par) || 0) + 1);
        hashMap.set(com, (hashMap.get(com) || 0) - 1);
    }
    for(let [i, j] of hashMap) {
        if(j > 0) {
            return i;
        }
    }
}

해시 알고리즘을 사용하여 문제를 해결한 코드입니다.

 

Map 객체를 사용하여 해시 테이블을 구현했습니다. 참가자 배열과 완주자 배열을 동시에 순회하면서 Map에 이름과 수를 저장하고, 완주자의 경우 해당 이름의 값을 1 감소시킵니다. 최종적으로 Map을 순회하면서 값이 0보다 큰 경우, 즉 완주하지 못한 선수의 이름을 반환합니다.

 

4차 시도 (성공)

// 4차 시도 (성공) - 해시 사용
function solution(participant, completion) {   
    let hashMap = new Map();
    
    for (let par of participant) {
        hashMap.set(par, (hashMap.get(par) || 0) + 1);
    }
    
    for (let com of completion) {
        hashMap.set(com, hashMap.get(com) - 1);
    }
    
    for(let [name, count] of hashMap) {
        if(count > 0) {
            return name;
        }
    }
}

3차 시도에서 참가자 배열과 완주자 배열을 따로 순회하도록 수정한 코드입니다.

 

먼저 참가자 배열을 순회하면서 Map에 이름과 수를 저장한 후, 완주자 배열을 순회하면서 해당 이름의 값을 1 감소시킵니다. 마지막으로 Map을 순회하면서 값이 0보다 큰 경우의 이름을 반환합니다.

 

이 방식이 가장 직관적이고 효율적인 방법으로 보입니다.

 

사족

이 문제를 통해 해시 알고리즘의 활용 방법과 Map 객체의 사용법에 대해 알 수 있었습니다. 문제의 조건을 잘 파악하고 적절한 자료구조를 선택하는 것이 중요하다는 것을 다시 한번 깨달았습니다.

 

또한, 코드를 리팩토링하면서 가독성과 효율성을 높이는 과정도 유익했습니다.