[Javascript][Programmers] 완주하지 못한 선수

 

문제

해당 문제를 해결하는 가장 간단한 방법은 하나씩 대조하며 완주하지 못한 사람을 찾는 것입니다. 완주자 목록에 있는 이름을 참가자 목록에서 하나씩 삭제하다보면 완주하지 못한 한 사람을 찾을 수 있게 됩니다. 가장 직관적인 방법은 두 배열을 정렬한 후 순서대로 비교하는 것입니다.

• 시간복잡도: O(NlogN)

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

이 방법은 간단하고 이해하기 쉽지만 대규모 데이터셋에서는 효율성이 떨어질 수 있습니다.

 

나의 풀이

더 효율적인 방법으로 해시 맵을 사용할 수 있습니다.

• 시간복잡도: O(N)

function solution(participant, completion) {
    const hashMap = new Map();
    
    for(let name of participant) {
        hashMap.set(name, (hashMap.get(name) || 0) + 1);
    }
    
    for(let name of completion) {
        let count = hashMap.get(name);
        if(count === 1) {
            hashMap.delete(name);
        } else {
            hashMap.set(name, count - 1);
        }
    }
    
    return hashMap.keys().next().value[0]
}

각 참가자의 이름을 키로, 등장 횟수를 값으로 하는 해시 맵을 생성합니다. 완주자 목록을 순회하면서 해당 이름의 카운트를 감소시키고, 최종적으로 맵에 남아있는 유일한 키가 완주하지 못한 선수의 이름이 됩니다.

 

다른 풀이

객체를 사용하여 해결할 수도 있습니다.

• 시간복잡도: O(N)

function solution(participant, completion) {
  // ➊ 해시 테이블 생성
  const obj = {};

  // ➋ 참가자들의 이름을 해시 테이블에 추가
  for (const p of participant) {
    if (obj[p]) {
      obj[p] += 1;
    } else {
      obj[p] = 1;
    }
  }

  // ➌ 완주한 선수들의 이름을 키로 하는 값을 1씩 감소
  for (const c of completion) {
    obj[c] -= 1;
  }

  // ➍ 해시 테이블에 남아 있는 선수가 완주하지 못한 선수
  for (const key in obj) {
    if (obj[key] > 0) {
      return key;
    }
  }
}

 

---

Reference

코딩테스트 합격자되기: 자바스크립트 편