feat: [Lv. 1] 완주하지 못한 선수 (JS/TS)

https://school.programmers.co.kr/learn/courses/30/lessons/42576

1. 문제분석
입력리스트에서 출력리스트를 제외한 결과 리턴 -> 결과는 정확히 1개
-> N은 10만 이하, 각 항목은 알파벳 소문자 20자 이내, 중복값 존재
맵으로 참가자 개수를 세고, 완주자 마이너스를 친다
맵 더하는 데 N + 맵 빼는 데 N-1 + 맵 탐색하는 데 1 -> O(N)

2. 풀어보기
["leo", "kiki", "eden"] -> leo 1, kiki 1, eden 1 -> ["eden", "kiki"] -> leo 1, kiki 0, eden 0 -> "leo"
["marina", "josipa", "nikola", "vinko", "filipa"] -> marina 1, josipa 1, nikola 1, vinko 1, filipa 1 -> marina 0, josipa 0, nikola 0, vinko 1, filipa 0 -> "vinko"
["mislav", "stanko", "mislav", "ana"] -> mislav 2, stanko 1, ana 1 -> mislav 0, stanko 0, ana 0 -> "mislav"

3. 슈도코드
participant[] 돌려서 -> count_by_name[]에 0 추가하고 플러스
-> completion[] 돌려서 -> count_by_name[] 마이너스 -> 남은 게 0이면 아예 키도 삭제
count_by_name에 남은 name 뽑아서 리턴

 

4. 구현코드

const solution = (participant: string[], completion: string[]): string => {
  const count_by_name = new Map<string, number>();
  addParticipant(participant, count_by_name);
  removeCompletion(completion, count_by_name);

  return count_by_name.keys().next().value; // HACK 1개 보장됨
};

const addParticipant = (participant: string[], count_by_name: Map<string, number>) => {
  for (const name of participant) {
    const count = (count_by_name.get(name) ?? 0) + 1;
    count_by_name.set(name, count);
  }
};

const removeCompletion = (completion: string[], count_by_name: Map<string, number>) => {
  for (const name of completion) {
    const count = (count_by_name.get(name) ?? 0) - 1;
    if (count === 0) {
      count_by_name.delete(name);
    } else {
      count_by_name.set(name, count);
    }
  }
};

 

5. 풀이회고

처음엔 참가자에서 완주자를 지우는 방식을 생각했는데, 생각해보니 O(N^2)이 되서 효율성 테스트가 터졌을 것 같다.

문제 자체가 해시 유형에 속한 문제여서, 해시로 생각하니 O(N)만에 풀렸다.

해시는 O(1)~O(logN)이니, 사용할 수 있는 상황에서는 먼저 고려해볼 수 있는 방법인 것 같다.