프로그래머스: 완주하지 못한 선수

(문제링크)

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명
예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

첫번째 풀이

해당 문제가 해쉬 문제로 분류되어 있길래 Map을 사용해서 풀었다.

Map이란?
key와 value로 구성된 자료구조이다.
key와 value를 저장하면 key만으로 value를 불러올 수 있다.
key와 value 값에는 어떤 값이든 들어갈 수 있다. (심지어 key를 배열로 저장할 수 있다..)
Map은 Iterable이므로 for...of 반복문이 가능하다. Map이 Iterable인 것은 Map과 Object와의 큰 차이점이다.

Map에 참가자 이름과 해당 참가자 이름의 수를 저장한뒤, 완주한 사람의 이름과 비교해서 완주하지 못한 사람을 찾아냈다.
Map에 참가 여부가 아닌 참가자 이름의 수를 저장하는 이유는, 같은 이름이 여러개일 수 있다는 조건 때문이다.

1. Map을 사용해서 participant 배열의 모든 값을 key: 참가자 이름, value: 참가자 이름의 수 로 저장한다.

2. completion 배열을 순회하면서 Map에서 해당하는 이름의 value를 감소시킨다.

3. Map의 value 중 0이 아닌 것을 검사해서 완주하지 못한 선수의 이름을 찾아낸다.

소스코드

function solution(participant, completion) {
    let map = new Map();
  	
  	// Map에 {key: 참가자 이름, value: 참가자 이름의 수} 저장
    for(let i=0; i<participant.length; i++){
        if(!map.has(participant[i])){
            map.set(participant[i], 1);
        }else{
            map.set(participant[i], map.get(participant[i]) + 1);
        }
    }
    
  	// completion의 참가자 이름의 수만큼 감소
    for(let i=0; i<completion.length; i++){
        map.set(completion[i], map.get(completion[i]) - 1);
    }
    
  	// Map을 순회하여 참가자 이름의 수가 0이 아니라면 key 반환
    for(let [key, value] of map){
        if(value !== 0) return key;
    }
}

테스트 결과

두번째 풀이

첫번째 풀이를 보고 participant와 completion의 개수를 합친 만큼 set과 get을 반복하는 것이 시간을 잡아먹지 않을까 하는 의문이 들었다.
좀 번거로워 보이기도 했다.

그래서 Map을 사용하지 않고 풀어봤다.

내가 사용한 방법은 participant와 completion을 정렬한 뒤, 같은 인덱스의 값을 비교해서 값이 다르다면 return 하는 방법이다.

소스코드

function solution(participant, completion) {
  	// 사전순 정렬
    participant.sort();
    completion.sort();
    
  	// participant 와 completion 의 값을 비교해서 같지 않다면 return
  	//    participant보다 completion의 값이 더 작으므로 participant.length-1 까지 반복
    for (let i=0; i<participant.length-1; i++) {
        if (participant[i] !== completion[i]) return participant[i];
    }
  	// 반복문을 다 돌아도 없다면 participant의 가장 마지막 값이 답
    return participant[participant.length-1];
}

테스트 결과

느낀점

코드 자체는 두번째 풀이가 더 간결하지만 시간 효율은 첫번째 풀이가 더 좋았다.

두번째 풀이에서 가장 시간을 잡아먹는 것은 두번의 sort 였다.
생각해보니 sort는 정렬이라 자료의 크기가 클수록 시간을 잡아먹는데 생각을 못했다..

이렇게 된 김에 sort의 시간복잡도를 찾아봤다.

Javascript Array.sort() 시간복잡도
평균: $O(nlog(n))$
최악: $O(n^2)$

와 최악의 경우 정말 오래걸린다 !

배운점,
자료의 크기가 클 경우 sort의 사용을 최소화하자.

+
Map의 시간 효율도 알아보고 싶어서 Map.set()의 Javascript 명세를 들어가봤지만 너무 어려웠다.. 😂
Javascript의 동작을 꿰뚫고 있는 개발자가 되고 싶지만 갈 길이 먼 것 같다...!