완주하지 못한 선수

조건 :

• 1. participant.length = completion + 1
• 2. participant 중 동명이인이 있을 수 있다. (중복 가능)
• 반환:  (participant but not completion)

두 가지 자료구조, Array와 Hash로 접근이 가능하다.

1. Array로만 접근하는 관점이다. 두 개의 array를 비교하기 위해서 이중 반복문을 사용할 수도 있지만 이는 O(n2)이 걸리기 때문에 제쳐두고 sort 하여 인덱스 순서대로 비교한다 

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

2. Hash와 Array 모두 사용한다.

"참가자 이름(key), 참가자 수(value)로 구성된 Hash를 만들고, 완주한 참가자의 수는 참가자수를 1씩 지워 최종적으로 참가자수가 0이 아닌(complete X) 참가자 이름을 반환하기

1. 배열로 구성된 participant를 key-value(참가자 이름, 참가자 수)로 구성된 hash 만들기 
2. completion 배열을 돌면서  completion에 있는 모든 참가자를 hash에서 찾아 참가자수를 -1한다.  
3. 참가자수가 0이 아닌 참가자 이름 반환하기
   

function solution(participant, completion){

  //make dictionary
  var dic2 = participant.reduce((obj, name)=>
  	(obj[name] = obj[name] ? obj[name]+1: 1, obj), {});

  //compare
  for(let i=0; i < completion.length; i++{
  	dic[completion[i]]--;
  }

  //find !completed
  return participant.find( name => dic[name] != 0)
}
   

 

혹은 어차피 participant에서 return 값이 나오기 때문에 participant을 기준으로 for문을 돌고 그 전에 completion을 hash로 만들 수도 있다. find는 true가 나오는 첫번째 원소를 반환하기 때문에 completion으로 만든 hash와 모두 비교를 마치고 남은 participant 원소를 반환하도록 하면 된다.

function solution(participant, completion) {
    var dic = completion.reduce((obj, t)=> (obj[t]= obj[t] ? obj[t]+1 : 1 , obj) ,{});
    return participant.find(t=> {
        if(dic[t])
            dic[t] = dic[t]-1;
        else 
            return true;
    });
}

 

 

* 사실 문제를 못 풀다가 위의 코드를 보고 너무 예뻐서 함수형 프로그래밍 책 중 이 파트만 하루 공부했다. 아직 푸는 데에 시간이 오래 걸리지만 더 많이 공부해야겠다.