문제설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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" |
풀이
처음에 제출했던 풀이
function solution(participant, completion) {
completion.forEach((a)=>{
participant.splice(participant.indexOf(a),1)
// participant내 a값의 인덱스 번호에서 부터 1개를 잘라낸다.
})
return participant[0]
}.forEach()로 completion을 돌면서 participant 내에 일치하는 값을 .splice()로 잘라내는 방식으로 풀었다. 이렇게 하면 동명이인이 있더라도 한 명씩만 잘라내기 때문에 문제없는 풀이라고 생각했고 코드실행에서도 잘 통과 했다. 그런데 제출했더니 시간초과가 나와버렸다.
* 시간복잡도 : 문제를 해결하는데 걸리는 시간과 입력한 함수 관계로, "연산의 횟수"(시행 횟수)를 센다.
찾아봤더니 .forEach()문으로 이 문제를 해결하면 시간복잡도가 높아 시간초과가 나는 것이었다. 어떻게 풀어야할지 머리를 싸매다가 아주 단순한 방식이 먹힌다는 것을 알게됐다.
다시 제출한 풀이
function solution(participant, completion) {
participant.sort()
completion.sort() // 두 배열 모두 사전순으로 정렬
for(let i = 0; i < participant.length; i++){
if(participant[i] !== completion[i]){
return participant[i] // 인덱스 순으로 비교하다 일치하지 않을 시 return
}
}
}설명
participant와 completion 두 배열 모두 .sort()로 사전순으로 정렬해준다. 그리고 대응하는 인덱스끼리 비교하다 일치하지 않을 때 return해준다.
단순하면서도 훌륭한 풀이였지만 좀 허무한 마음에 다른 풀이는 없나 찾아 보았다. 그러던 중에 발견한 것이 있어 추가적으로 남겨두고 싶다.
다른 사람의 풀이
var solution=(_,$)=>_.find(_=>!$[_]--,$.map(_=>$[_]=($[_]|0)+1))아니 이건 도대체 뭘까? 정규분포식인가? 어떻게 이걸 한줄에 풀지?하는 생각들을 하며 댓글을 보다보니 사실 이 풀이는
var solution=(participant,completion)=>participant.find(name=>!completion[name]--,completion.map(name=>completion[name]=(completion[name]|0)+1))이 코드의 변수명을 minify한 것이었다. 그런데 이렇게 두고봐도 이해할 수 없는 것들이 많았고, 마침 댓글에 친절하게 해석(?)을 해주신 분들이 있어 그 내용을 정리해보려 한다.
1
먼저 participant.find(콜백함수,콜백함수에 this로 사용될 객체) 이렇게 두 가지의 매개변수가 주어진 것인데 여기서 뒤쪽에 주어진 함수가 콜백함수보다 먼저 실행된다. 여기서 콜백함수가 하는 역할을 살펴보자면, 사실 원래 .map()은 일반적으로 현재 처리할 요소를 파라미터로 받아 콜백함수를 돌아가며 실행해서 새로운 배열을 return하는데 사실 여기서 return되는 배열은 특별히 의미가 없다. 그보다는 .map()함수가 먼저 실행된다는 것이 중요하다. 즉, 가독성 좋게 앞으로 빼내어서 정리하자면 다음과도 같다고 할 수 있다.
var solution = (participant,completion) => {
completion.map(name => completion[name] = (completion[name]|0)+1)
return participant.find((name) => !completion[name]--)
}2
그렇다면 .map()에서 어떤 역할을 하는지 살펴보자. 여기서 name은 completion의 각 요소들을 의미하고 이것을 가지고 completion[name]을 정의(=)하고 있는데, 여기서 의문이 생긴다. 'completion[name]=' 이러한 방식으로 key에 value를 할당하는 것은 dictionary에서 하는 것이고, completion은 배열인데 어떻게 이런게 가능한걸까. 댓글로 설명해주시는 것을 읽고 가장 신기했던 것이 이 부분인데, 사실 자바스크립트의 배열은 객체이다. 실제로 배열을 typeof로 확인해보면 'object'가 나온다. 따라서 dictionary에서 처럼 key를 정의하여 value를 할당해주면 아래와 같이 배열 내에도 포함되는 것을 알 수 있다.
let fruit = ['apple','grape','banana']
console.log(typeof fruit) // 'object'
fruit['apple'] = 3
console.log(fruit) // ['apple','grape','banana', apple: 3]
그러므로 위의 completion[name] = (completion[name]|0)+1 은 completion 객체 중 name이라는 key의 value를 정의하는데, 만약 completion 객체 내에 name이라는 key의 value가 이미 존재한다면 그 value를 없다면 0을 뱉어내고(OR문) 거기다가 1을 더해주라는 뜻으로 이해할 수 있다. .map()이 다 돌고 나면 completion에 작업이 끝난 상태로 앞부분엔 모든 이름이 String으로 들어있고, 그에 이어서 각 이름의 개수가 key-value 페어로 들어있다.
3
이제 .find()를 살펴보자. 먼저 .find()는 조건에 true인 첫번째 요소를 return한다. 그렇다면 어떤 경우에 true가 될까? completion[name]은 그 해당 이름의 개수를 불러온다. 그런데 여기서 !는 뒤의 값을 "boolean"으로 바꿔주는데, 반대로 바꿔준다. !true면 false가 나온다. 즉 value가 1일 경우 !1로 false가 된다. 반대로 !0은 true가 된다. 자바스크립트에서 false가 되는 value는 7개(false, 0, -0, NaN, null, undefined)로 다음과 같은 값들이 !로 인해 true가 되는 것이다. 그리고 다음은 -- 인데 1을 삭감하는 것으로 '후치'이다. 현 상황에서 completion[name]의 value로 나올 수 있는 값은 1 또는 0 또는 undefined인데 1의 경우 false가 나온 뒤 1이 삭감될 것이고, 동명이인이 있어 0이 나온경우 true를, 원래 completion에 존재하지 않아 값이 없다면 undefined가 나온 경우에도 값이 true가 되어 그 key값을 최종 return하게 된다. 여담으로 undefined에 후치로 --를 해주면 key와 value가 생기게 되고 value는 NaN으로 배열에 들어간다.
let fruit = ['apple','grape','banana']
console.log(!1) // false
console.log(!0) // true
!fruit['banana']--
console.log(fruit) // ['apple','grape','banana', banana: NaN]
마무리
댓글을 읽고 이해하는 데에 시간이 많이 걸렸다 보니 글이 괜히 길어진 것 같지만, 지금은 이해했다고 생각하고 나중엔 또 머리 벅벅 긁고 있을 나를 위해 나름대로 상세하게 써보았다.
