Level1 - 완주하지 못한 선수

문제 출처

Solution

효율성 검사 실패

function solution(participant, completion) {
  completion.forEach(el => {
    let idx = participant.indexOf(el)
    participant.splice(idx, 1)
  });
  return participant[0]
}

completion에 담긴 모든 요소에 대해서 participant에 있을 경우 해당 인덱스를 찾아서 배열에서 제거해주는 방식으로 풀었을 때, 효율성 검사를 통과하지 못한다.

indexOf는 호출될 때마다 0번 인덱스부터 완전 탐색을 통해서 요소를 탐색하기 때문에 completion과 participant의 요소가 많으면 시간이 오래 걸릴 수 밖에 없다.

효율성 검사 성공

function solution(participant, completion) {
  var answer = ''
  let part = Object()
  participant.forEach(el => {
    if (part[el] === undefined) {
      part[el] = 1
    } else {
      part[el]++
    }
  });
  completion.forEach(el => {
    part[el] -= 1
  });
  const part_key = Object.keys(part)
  const part_value = Object.values(part)
  answer = part_key[part_value.indexOf(1)]
  return answer
}

1. participant의 요소를 key로 하여 해당 key값의 개수만큼 value를 가지는 part Object 생성
2. completion의 요소를 key로 하여 해당 key값의 개수만큼 part의 value값을 하나씩 차감
3. part의 key와 value를 가지는 배열을 각각 생성
4. part_value에서 값 1에 해당하는 요소의 인덱스와 같은 인덱스의 part_key값 반환

효율성 검사는 key값으로 value값에 바로 접근할 수 있는 Object를 이용해서 해결했다. Object를 이용하면 participant과 completion에 동일한 요소가 있을 수 있다는 문제의 제약사항을 해결할 수 있다. key : value 형태로 접근하면 시간 복잡도가 O(1)이기 때문에 쉽게 찾아서 값을 변경할 수 있다.

participant가 N개의 요소를, completion이 M개의 요소를 가진다고 했을 때, 효율성 검사를 통과하지 못한 코드는 (N*M) 번의 탐색이 필요하고, 효율성 검사를 통과한 코드는 최대 (2N+M)번을 탐색한다.