완주하지 못한 선수

 

코드

각 이름을 비교해서 같으면 배열에서 삭제하는 방법

function solution(participant, completion) {
  for (let i = 0; i < participant.length; i++) {
    for (let j = 0; j < completion.length; j++) {
      if (participant[i] === completion[j]) {
        participant.splice(i, 1);
        completion.splice(j, 1);
        i--;
        j--;
        break;
      }
    }
  }
  return participant[0];
}

이 코드는 시간복잡도 O(N^2)인데 정확성 통과는 했지만 효율성에서 막혔다

 

수정 코드

완주자을 순회하면서 완주자의 이름을 참가자에서 찾아서 삭제

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

더 빠를 줄 알았는데 idexOf 자체가 결국은 순회해야해서 아까와 같은 O(N^2)이다.

역시 통과 못함

 

통과 코드

오름차순후 비교

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

문제를 잘 읽어보면 통과하지 못한 사람이 1명으로 명시되어있으므로

두 배열을 오름차순을 한후에 같은 index를 비교하다가 다르다면 그 사람이 완주 못한 선수

완주자 끝까지 다 똑같다면 참여자의 마지막이 완주 못한 선수이다