[Lv1] 완주하지 못한 선수

프로그래머스

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

나의 풀이(1)

이 첫 번째 풀이법은 while문에서 반복문이 실행되고, while문 내에서 findIndex로 배열을 순회하고, 마지막에 참가자 배열에서도 find로 배열을 순회한다. 따라서 선형탐색이 중첩되거나 여러번 발생해 효율성 테스트를 통과하지 못한 것 같다.

• 테스트케이스는 통과했지만 효율성 테스트는 하나도 통과 못함
• 완주자 배열이 빈배열이 될때까지 다음을 반복한다.
  • 변수 idx에 참가자 배열에서 존재하는 완주자 배열의 0번째값 인덱스를 저장한다. (여기서 사용된 findIndex는 배열에 동일한 값이 존재해도 첫번째 값의 인덱스를 리턴한다. 없으면 -1을 리턴한다.)
  • 참가자 배열의 해당 idx 인덱스 값을 0으로 만든다.
  • 완주자 배열의 0번째 값을 삭제한다.
• 완주하지 못한 참가자는 1명 뿐이므로 참가자 배열에서 유일한 데이터타입인 문자열을 찾아 리턴한다.

function solution(participant, completion) {
    //참여자 명단에 있지만, 완주자 명단에 없는 사람을 구한다
    //단, 동명이인이 있을 수 있다.
    while(completion.length){
        const idx = participant.findIndex(el => el === completion[0]);
        participant[idx] = 0;
        completion.shift();
    }
    return participant.find((el)=> typeof el === 'string');
}

나의 풀이(2)

문제에서 hash라는 힌트를 주고 있어서 해시에 대해 찾아보았고, 자바스크립트에는 hash table로 object를 사용할 수 있어 객체를 활용해 풀어 통과할 수 있었다.

• 모든 테스트케이스와 효율성 테스트 모두 통과!
• 참가자 배열에 저장된 참가자 이름을 키(key)로 갖고, 그 이름을 가진 인원을 값(value)으로 갖는 객체(hash)를 만든다.
• 참가자 배열을 순회하면서 hash[참가자 배열의 요소] 값이 1보다 크다면 --를 해주고, 그 외 경우는 1명일테니까 삭제시킨다.
• hash 객체에 남은 키값은 하나 뿐일테니 getOwnPropertyName으로 가져온 배열의 0번째 값을 리턴한다.

function solution(participant, completion){
  let hash = {};
  for(let i=0;i<participant.length;i++){
    if(hash[participant[i]]) hash[participant[i]]++;
    else{
      hash[participant[i]]=1;
    }
  }
  for(let i=0;i<completion.length;i++){
    if(hash[completion[i]]>1) hash[completion[i]]--;
    else{
      delete hash[completion[i]]
    }
  }
  return Object.getOwnPropertyNames(hash)[0];
}  

다른 사람 풀이

• 완주자 배열을 객체로 만든다.
  • obj[완주자 이름]가 undefined인 경우, obj[완주자 이름]=1을 하고, 이미 있다면, ++를 해준다.
  • 참가자 배열에는 있지만 완주자 객체에는 없는 값을 찾아 리턴한다.

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]--;
    else{
      return true;
    }
  });
}

그동안은 조건에 따라 삼항연산자의 두번째, 세번째 값을 리턴시켰는데, 여기서는 obj[t]에 값이 있으면, obj[t]에 ++를 해주고, 없다면 1을 할당해주고 있다.

그리고, find 메소드를 사용해 조건을 만족하는 true인 경우에 참가자 배열의 값을 바로 리턴시킨다.

hash Table

값을 hash function을 거쳐 hash code를 만들고, hash code에 따라 배열에 저장한다. 만약, 동일한 hash code를 가졌다면(colision), 배열 안에 또다른 배열을 만들어 저장한다.

값을 검색할때, hash code를 찾아 배열에 인덱스로 활용해 바로 찾을 수 있으므로 대게 O(1)의 시간복잡도를 갖고, 앞서 말한 colision이 발생했다면, 배열안의 배열을 선형탐색하면 되므로 O(n)만큼의 시간복잡도를 갖게된다.

이는 단순히 배열의 요소로 값을 할당해 매번 배열을 선형탐색하지 않아도 되므로 빠르고 편리하다.

reference

• https://www.youtube.com/watch?v=HraOg7W3VAM