완주하지 못한 선수 찾기 (해시 활용 문제)

 

완주하지 못한 선수 찾기 (해시 활용 문제)

프로그래머스에서 자주 등장하는 해시(Hash)를 활용한 문제 중 하나인 완주하지 못한 선수 찾기 문제

---

1. 문제 이해

📝 문제 설명

마라톤에 참가한 선수들의 명단(participant)과 완주한 선수들의 명단(completion)이 주어집니다.

하지만 단 한 명의 선수가 완주하지 못했습니다.

이를 찾아 반환하는 문제입니다.

 

제한 사항

• participant의 길이는 1 이상 100,000 이하입니다.
• completion의 길이는 participant보다 1 작습니다.
• 선수 이름은 1개 이상 20개 이하의 알파벳 소문자로 구성됩니다.
• 동명이인이 있을 수 있습니다.

✅ 입력 예시

participant = ["leo", "kiki", "eden"];
completion = ["eden", "kiki"];

✅ 출력 예시

"leo"

---

2. 해결 방법 추론

이 문제를 해결하는 몇 가지 방법을 고려할 수 있습니다.

❌ 브루트포스 (비효율적)

모든 participant를 completion과 비교하면서 찾을 수도 있지만, 시간 복잡도가 O(N²)가 되므로 비효율적입니다.

✅ 정렬 후 비교 ( O(N log N) )

1. participant와 completion을 정렬합니다.
2. 두 배열을 비교하여 차이가 발생하는 지점을 찾습니다.
3. 차이가 발생한 선수가 완주하지 못한 선수입니다.

function solution(participant, completion) {
  participant.sort();
  completion.sort();
  
  for (let i = 0; i < completion.length; i++) {
    if (participant[i] !== completion[i]) {
      return participant[i];
    }
  }
  return participant[participant.length - 1];
}

✅ 해시(Map) 활용 (O(N))

정렬 방법보다 효율적인 해시 맵(Hash Map)을 활용하는 방법을 사용하면 O(N)의 시간 복잡도로 해결할 수 있습니다.

1. Map 객체를 생성합니다.
2. participant 배열을 순회하며 map에 선수 이름을 키로, 등장 횟수를 값으로 저장합니다.
3. completion 배열을 순회하면서 map에서 해당 선수의 값을 -1 감소시킵니다.
4. 마지막으로 map을 탐색하며 값이 1인 선수를 찾습니다.

function solution(participant, completion) {
  const map = new Map();
  
  for (let name of completion) {
    map.set(name, (map.get(name) || 0) + 1);
  }

  for (let name of participant) {
    if (!map.get(name)) return name;
    map.set(name, map.get(name) - 1);
  }
}

✅ 예제 실행 과정

participant = ["leo", "kiki", "eden"];
completion = ["eden", "kiki"];

1️⃣ completion 저장 (map 초기화)

map = { eden: 1, kiki: 1 }

2️⃣ participant와 비교하며 감소

leo → map에 없음 → leo 반환 ✅

 

결과: "leo"

---

3. 시간 복잡도 분석

방법 시간 복잡도

브루트포스	O(N²)
정렬 후 비교	O(N log N)
해시(Map) 활용	O(N)

 

해시를 활용하면 가장 빠르게 해결할 수 있습니다.

---

4. 결론

이 문제는 해시(Map)을 이용하여 해결하는 것이 가장 효율적입니다. 해시를 사용하면 O(N)의 시간 복잡도로 빠르게 해결할 수 있으며, 정렬 방식보다 성능이 좋습니다.