[프로그래머스] 완주하지 못한 선수 - JavaScript

1. 문제

42576번 문제 보러가기

2. 오답

function solution(participant, completion) {
  let numbers = [];

  for (let i = 0; i < participant.length; i++) {
    numbers.push(participant[i]);
  }

  for (let i = 0; i < completion.length; i++) {
    if (numbers.includes(completion[i])) {
      numbers.splice(numbers.indexOf(completion[i]), 1);
    }
  }

  return numbers.join("");
}

위 코드는 시간 초과 오류를 가져온다.

for문을 2번 사용하였고 하나의 for문 안에 includes()를 사용하였기 때문에 총 시간복잡도는 O(n*n)이다.

3. 최종 풀이

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

sort()메소드 2개와 for문 하나를 사용함으로 총 시간복잡도는 sort()의 최악인 경우에 따라 O(nlogn)이 된다.

sort 시간복잡도

가장 많이 쓰이는 JavaScript Chrome V8의 경우 timesort를 사용한다. timesort의 시간복잡도는 다음과 같다.

최선 : O(n)
평균 : O(nlogn)
최악 : O(nlogn)

참고 링크 : https://d2.naver.com/helloworld/0315536