[프로그래머스 Lv.1] 완주하지 못한 선수

◼️ 문제

완주하지 못한 선수

1. 문제 설명

2. 제한사항

3. 입출력

◼️ 풀이

✏️ 전반적인 풀이과정

1. completion 배열(완주자 리스트)을 객체로 만든다.
2. participant 배열(참여자 리스트)을 for문으로 순회하며 completion 객체에 명단이 있는지 확인한다.
   2-1. 명단에 없다면 바로 결과를 반환한다.

📃 풀이과정 추가 설명

completion 객체 생성

2개의 배열을 2중 for문으로 돌면서 체크할 수 있지만 비효율적이기 때문에 빠르게 값을 찾아올 수 있는 객체를 사용하기로 결정했다.

객체 사용을 결정하면서 completion과 participant 중 어떤 배열을 객체로 만들것이냐를 고민했었는데, 아무래도 completion 객체가 더 빠르게 결과를 도출할 수 있을 것 같았다.

completion을 객체로 사용하는 경우,
participant 배열을 돌면서 completion 객체에 참가자 이름이 없거나, 혹은 동명이인 중 하나라도 완주를 못했다는 것을 발견하면 남은 participant 배열을 돌지 않아도 바로 결과를 리턴할 수 있다.

그러나 pariticpant를 객체로 사용하는 경우,
반드시 completion 배열을 다 확인해야하고, 최종적으로 도착하지 못한 참가자를 찾는 방식으로 구현해야 했기 때문에 비교적 효율이 좋지 못하다고 생각했다.

💻 코드

function solution(participant, completion) {
  const completionObj = {};

  for (const player of completion) {
    completionObj[player] = (completionObj[player] || 0) + 1;
  }

  for (const player of participant) {
    if (!completionObj[player]) {
      return player;
    } else {
      completionObj[player] -= 1;
    }
  }
}

◼️ 틀렸던 풀이

정확성 테스트는 통과했지만 효율성 테스트에서 전부 실패했다.

나중에 입출력 조건을 확인해보니 참가자 배열 크기가 최대 100,000이었는데,
이 점을 제대로 확인하지 못해 너무 단순하게 접근해버렸다.

이중 for문의 시간복잡도 O(N^2)인데 최대 10만개인 배열을 이중 for문으로 돌리려니...
효율성이 꽝인 것은 당연한 것이다.

💻 코드

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