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

프로그래머스 Level1 완주하지 못한 선수 문제

 

문제 풀이 : 참가자 명단(participant)과 완주자 명단(completion)을 비교하여 완주하지 못한 선수가

누구인지만 찾으면 되는 문제이다.

 

* 참가자중 동명이인이 있을 수 있다는 조건이 약간 까다로웠다.

 

처음에는 참가자 명단 for문을 돌면서 indexOf나 includes로 완주자 포함여부를 찾은뒤,

해결하는 로직으로 작성하였다. 제출을 하니 효율성 검사에서 시간초과 문제가 발생하였다.

즉, 이 문제는 시간복잡도도 고려해줘야하는 문제이다.  for문안에 indexOf를 사용했기에 O(n^2)의 복잡도를 가진다.

해결하기 위해서는 O(nlogN)이나 O(n)으로 해결해주어야한다.

 

* 다른 사람의 풀이를 보면 sort로 이용하여 푼 방법도있지만, 이 문제의 유형을 다루기 위해 정석적인 풀이로 풀었다.

 

그래서 다시 문제를 파악했는데, 해시 유형인것을 파악할수 있었다.

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행되는 자료구조이다.

검색시 key와 value의 쌍으로 검색되기 때문에 O(1)에 가깝다.

 

그러면 3단계로 나눠서 해당 문제를 해결해주면된다.

1. 참가자 명단(participant)을 순회하면서 key: 선수이름 value: +1로 Map을 이용해 key, value쌍으로 만들어준다.

 

2. 완주자 명단(completion)을 순회하면서 Map함수에 key(선수이름)이 있을시, value: -1을 해준다.

 

3. 2번의 과정을 마치고 나면 완주를 한 선수의 value값은 0이 될것이고, 그외에는 1이상일것이다.

그래서 value값이 1이상일때 해당 선수의 이름을 answer값에 넣어주고 리턴해준다.

 

 

* 참고 : https://velog.io/@noyo0123/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-javascript-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98-otk2fxojro