문제

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

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

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

시도 1

completion 배열을 순회하며 completion 배열을 요소를 participant에서 삭제하도록 하였다. 순회 후 participant 배열에 남은 1개의 요소가 정답

function solution(participant, completion) {
  var answer = participant
  
  completion.map(x => {
    var index = participant.findIndex(x)
    answer = answer.splice(x, 1)
  });
  
  return participant[0]
}

결과: Time out

정확성 테스트는 다 통과하였으나, 시간 테스트는 하나도 통과하지 못했다.

participant의 원소 수를 m, completion의 원소 수를 m-1이라고 했을 때, 시간복잡도는 O(m^2)가 나온다.

completion.map(x => { // O(m-1)
  var index = participant.findIndex(x) // O(m)
  answer = answer.splice(x, 1)
});
// => O(m * (m-1)) = O(m^2)

O(m)이 나오도록 구현해야 하는 것 같다.

시도 2

*다른 사람의 풀이 참고

completion을 순회하며 갯수를 count한 dictionary를 만든다.
이후 participant를 순회하며 dictionary에서 key가 participant의 요소인 항목을 찾는다.

찾은 항목의 value를 1씩 뺀다. 만일 value가 0인 경우 해당 항목의 key가 정답

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;
    }
  });
}

결과: 정확성, 효율성 통과

---

문제를 풀면서 javascript의 함수에 대해 다시 꼼꼼하게 공부할 수 있었다.

reduce(), 쉼표 연산자

var dic = completion.reduce((obj, t) => ( 
  obj[t] = obj[t] ? obj[t] + 1 : 1, 
  obj
), {});

문제에서 이 부분이 잘 이해되지 않았다.
기본적인 reduce의 callback이 (acc, curr) => return(value)로 알고 있는데, callback 부분이 (obj, t) => ( ... , obj) 이런 구조로 되어있었기 때문이다.

다른 optional parameter가 있는 건가 했는데, 쉼표연산자였다.
따라서 ob[t]를 변환 후 오른쪽에 있는 obj를 반환하는 표현식이었다.

var names = ['Alice', 'Bob', 'Tiff', 'Bruce', 'Alice'];

var countedNames = names.reduce(function (allNames, name) {
  if (name in allNames) {
    allNames[name]++;
  }
  else {
    allNames[name] = 1;
  }
  return allNames;
}, {});
// countedNames is:
// { 'Alice': 2, 'Bob': 1, 'Tiff': 1, 'Bruce': 1 }

위의 코드는 MDN reduce 문서의 객체 내의 값 인스턴스 개수 세기 예시코드인데, 문제풀이의 코드와 구조는 동일하지만 보다 이해하기 쉽게 작성되어 있다.