PR-완주하지 못한 선수

goody·2021년 1월 23일
0

알고리즘

목록 보기
17/58

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

  • 제한사항
    마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
    completion의 길이는 participant의 길이보다 1 작습니다.
    참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
    참가자 중에는 동명이인이 있을 수 있습니다.

예시

|participant|completion|return|
|:----------|:---------|:-----|
|["leo","kiki","eden"]|["eden","kiki"]|"leo"|
|["marina","josipa","nikola","vinko","filipa"]|["josipa","filipa","marina","nikola"]|"vinko"|
|["mislav","stanko","mislav","ana"]|["stanko","ana","mislav"]|"mislav"|

풀이

  • completion에는 있고 participant 에는 없는 하나의 원소를 찾아내는 문제이다.
  • while문과 for문을 3~4개쯤 중첩하면 검색 효율성 면에서 빵점을 맞을 수 있다.
  • 자료구조 중 데이터 검색에 O(1) 의 시간복잡도를 갖고 있는 Hash Table을 쓰자.
  • participant 배열 내 원소를 key로 갖는 객체를 생성한다.
  • 객체의 value 는 1로 초기화하고, 동명이인이 나올 때마다 value1 씩 더한다.
  • 객체의 keycompletion의 원소를 비교해서, 일치할 때마다 해당 keyvalue를 1씩 뺀다.
  • 객체 내에서 value1 인 원소를 반환한다.

코드

function solution(participant, completion) {
    let runners = {};
    
    participant.forEach((e) => {
        if(runners[e]) {
            runners[e]++;
        } else {
            runners[e] = 1;
        }
    })
    
    for(let i = 0; i < completion.length; i++) {
        runners[completion[i]]--;
    }

    for(let i in runners) {
        if(runners[i] === 1) {
            // console.log(i);
            return i;
        }
    }
}

0개의 댓글