수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
나의 풀이
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.join();효율성 떄문에 약간 애를 먹은 문제이다. 처음에는 이런 식으로 값을 하나하나 비교한 다음 중복되지 않은 값을 삭제하는 식으로 풀었는데, 시간이 너무 오래 걸려서 효율성 문제에서 탈락했다.
function solution(participant, completion) {
const participants = participant.sort()
const completions = completion.sort()
let answer = '';
for(let i = 0; i < participants.length; i++)
if(participants[i] !== completions[i]){
answer = participants[i];
break;
}
return answer;
}그래서 이런식으로 정렬을 해 준뒤 풀었다. 정렬을 해준 다음, 값을 비교하여 똑같은 인덱스의 값이 같지 않다면 그 값을 인출하게 만들어 주었다.
참고할 풀이1
function solution(participant, completion) {
participant.sort();
completion.sort();
for(let i in participant) {
if(participant[i] !== completion[i]) return participant[i];
}
}이 풀이를 보니 괜히 변수에 정렬된 값을 넣어 줬다 싶었다. sort()함수는 원배열을 정렬하기 때문에 굳이 변수에 넣지 않아도 된다. 그리고 나는 다른 값을 하나 발견하고 나서도 검사를 계속 하길래 break를 넣어줬는데, 변수에 할당 안하고 바로 리턴해주면 되는 문제였다.
참고할 풀이2
function solution(participant, completion) {
const map = new Map();
for(let i = 0; i < participant.length; i++) {
let a = participant[i],
b = completion[i];
map.set(a, (map.get(a) || 0) + 1);
map.set(b, (map.get(b) || 0) - 1);
}
for(let [k, v] of map) {
if(v > 0) return k;
}
return 'nothing';
}해시에 관해 전혀 몰라서 해시에 대한 공부를 살짝 했다. 해시는 배열과 유사한 개념이다. 배열에서 값을 찾을 때는 반복문을 활용해서 배열의 값을 하나하나 검색해 줘야하지만, 해시는 값을 key와 value로 저장하여 key값을 찾기만 하면 그에 맞는 value값을 주어 검색 시간이 짧아진다는 장점이 있다.
여기서는 javascript의 표준 내장 객체인 Map()을 사용해 주었다. 여태까지 사용했던 Map()은 array의 메소드라서 살짝은 다른 개념이다.
이 map()에는 기능이 여러가지 있는데, 여기서 사용해 준 것은 set()과 get()이다. set()은 map()에다 값을 저장해주는 함수이고, 인수로 key와 value의 값을 받는다. get()은 값이 Map()에 있는지 확인해주는 함수인데, key값을 인수로 넣으면 value값을 인출, 없다면 undefined를 인출해 준다.
for(let i = 0; i < participant.length; i++) {
let a = participant[i],
b = completion[i];
map.set(a, (map.get(a) || 0) + 1);
map.set(b, (map.get(b) || 0) - 1);
}participant와 completion의 값을 순회하기 위해서 반복문을 써 줬고, 각각의 값을 변수 a와 b에 담아 줬다. 처음에 key값으로 a를 넣고, a가 map()에 존재하는지 확인한 다음 참이라면 그 값을, 거짓이라면 오른쪽의 값을 인출하도록 단축평가를 이용해 줬다. 참고로 단축평가 ||(OR)은 왼쪽의 값이 참이라면 왼쪽 값을 인출하고, 거짓이라면 오른쪽의 값을 인출한다. 여기서 만약 a의 값이 map()에 존재하지 않는다면 undefined는 false로 간주하므로 오른쪽 값 0이 인출된 다음, 1을 더한 값 즉 1이 map에 들어가게 된다. 맨 처음 값은 [leo, 1]이런 식으로 저장될 것이다. 그래서 value값은 겹치지 않는다면 1이 될 것이고, 만일 동명이인이 있다면 value는 1을 더한 2일 것이다.
그 다음 다시 b값을 map에 넣어 주는데, key값이 겹친다면 map.get(b)인 1 혹은 2가 나올 것이고 거기에서 -1를 해주게 된다. 이런식으로 하다 보면 결국 이름이 겹치면 0, 이름이 두 번 나왔으면 1을 인출할 것이다.
console.log(map);
/*Map(6) {
'marina' => 0,
'josipa' => 0,
'filipa' => 0,
'nikola' => 0,
'vinko' => 1,
undefined => -1
}
*/따라서 0보다 큰 값을 인출해 주면 완주하지 못한 사람을 찾게 되는 것이다. 해시를 사용하면 그냥 값을 하나하나 비교해주는 것보다 시간이 덜 든다.
해시를 사용한 경우 시간
값을 하나하나 검사한 경우 시간
