코딩테스트 해시(hash) 문제 - 완주하지 못한 선수 문제 원리 및 풀이

코딩테스트 해시(hash) 문제 - 완주하지 못한 선수 문제 원리 및 풀이

 

 

마라톤 경기는 참가자 모두에게 도전의 장입니다. 하지만, 모든 참가자가 완주하는 것은 아닙니다. 프로그래밍 문제로 치면, 이러한 상황은 배열과 해시 맵을 활용해 해결할 수 있는 좋은 예입니다.

 

이번 글에서는 마라톤에 참가했지만 완주하지 못한 한 명의 선수를 찾는 문제를 통해, 배열과 해시 맵의 활용 방법을 소개합니다. 문제 해결 과정을 통해, 여러분은 데이터 구조의 중요성과 함께, 문제를 효율적으로 해결하는 데 필요한 알고리즘적 사고를 배울 수 있을 것입니다. 이 지식은 여러분이 앞으로 맞닥뜨릴 수 있는 다양한 프로그래밍 문제를 해결하는 데 큰 도움이 될 것입니다.

 

 

코딩테스트 해시 문제 - 완주하지 못한 선수

 

문제 소개

프로그래머스

 

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어집니다. 여러분의 목표는 완주하지 못한 한 명의 선수의 이름을 찾아 반환하는 것입니다.

 

이 문제의 핵심은 참가자 중 동명이인이 있을 수 있다는 점입니다. 이로 인해 단순 배열 비교만으로는 해결할 수 없으며, 각 선수의 이름을 키로 하고, 그 이름이 배열에 나타난 횟수를 값으로 하는 해시 맵을 활용해야 합니다.

 

 

필자의 풀이 방법

function solution(participant, completion) {
    let participantMap = new Map();

    participant.forEach(name => {
        if (participantMap.has(name)) {
            participantMap.set(name, participantMap.get(name) + 1);
        } else {
            participantMap.set(name, 1);
        }
    });

    completion.forEach(name => {
        if (participantMap.has(name)) {
            let count = participantMap.get(name) - 1;
            if (count === 0) {
                participantMap.delete(name);
            } else {
                participantMap.set(name, count);
            }
        }
    });

    for (let [name, count] of participantMap) {
        if (count > 0) {
            return name;
        }
    }
}

 

위 코드는 참가자 이름을 키로 하고 동명이인 수를 값으로 하는 Map 객체(participantMap)를 생성합니다. 이후 완주한 선수의 이름을 이용해 Map에서 해당 이름의 값을 감소시키고, 마지막에 Map에 남은 선수의 이름을 반환합니다. 이 방법은 각 선수의 이름이 배열에 나타난 횟수를 정확하게 관리할 수 있게 해주어, 동명이인 문제를 해결할 수 있습니다.

 

 

다른 사람의 풀이 분석

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

    for(let i = 0; i < participant.length; i++) {
        let a = participant[i], 
            b = completion[i];

        map.set(a, (map.get(a) || 0) + 1);
        map.set(b, (map.get(b) || 0) - 1);
    }

    for(let [k, v] of map) {
        if(v > 0) return k;
    }

    return 'nothing';
}

 

다른 여러 풀이가 있었지만 이 코드가 가장 인상적이여서 추가해보았습니다. 이 풀이는 참가자와 완주자 배열을 동시에 순회하면서, 각 이름에 대해 참가자는 +1, 완주자는 -1을 해서 Map에 저장하는 방법입니다. 이렇게 하면, 결국 완주하지 못한 선수의 이름에 대응하는 값만이 양수로 남게 됩니다.

 

이 과정에서 중요한 점은 동명이인 처리가 자연스럽게 이루어진다는 것입니다. 동명이인이 있을 경우, 해당 이름에 대해 +1과 -1의 과정이 반복되어 최종적으로 완주하지 못한 선수의 이름만이 양수 값을 가지게 됩니다.

 

이 코드의 핵심은 간결성과 효율성에 있으며, 한 번의 순회로 문제를 해결하는 데 필요한 모든 정보를 Map에 구성하는 방식입니다.

 

---

 

끝으로

이번 글에서는 마라톤에 참가했으나 완주하지 못한 선수를 찾는 문제를 통해, 배열과 해시 맵을 활용하는 방법을 배웠습니다. 문제 해결 과정에서 해시 맵을 사용하여 데이터를 효율적으로 관리하는 방법을 학습할 수 있었습니다.

 

프로그래밍에서 데이터 구조의 선택은 문제 해결 과정의 효율성을 크게 좌우합니다. 이번 학습을 통해 여러분이 더 복잡한 문제에 직면했을 때, 적절한 데이터 구조를 선택하여 효과적으로 문제를 해결할 수 있는 능력이 향상되기를 바랍니다. 앞으로도 다양한 문제를 해결하며 여러분의 프로그래밍 역량을 지속적으로 키워나가길 기대합니다.

 

▼ 아래 문제도 풀어보세요! ▼

 

코딩테스트 해시(hash) 문제 - 폰켓몬 풀이 과정 및 리팩토링

 

프로그래머스 피보나치 수 문제풀이, 해설