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

https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=javascript 

프로그래머스

---

1) 풀이

이 문제를 처음 봤을 때는 그냥 participant에 filter 함수 사용해서 completion 에 현재 value가 포함되어 있지 않은 것을

걸러내고 그것을 return 해주고자 했다! 하지만 이렇게 하니까 두가지 문제가 생겼다

 

1. 테스트 3과 같은, 동명이인이 있는 경우 잘못 작동 (includes 함수를 사용해서 포함되어 있는 여부만 체크해주었다)

2. 효율성 테스트에서 전부 시간초과 뜸 (아마 filter 함수 + includes 다 보니 O(n^2) 이라 그런 거 아닐까..?)

 

그래서 filter 함수를 사용하되, completion 함수에 participant의 요소가 있을 경우 그 요소를 splice로

삭제해주고 요소가 없는 경우만 return 해주는 코드로 다시 바꿔서 해보았다

이 경우에 동명이인 문제는 해결되었지만, 여전히 효율성 테스트에서 모두 시간초과가 났다

 

이 문제 분류가 '해시' 라고 되어있는 것으로 보아, 시간적인 효율성이 중요하다고 생각해서 Map 을 이용해보았다

Map을 이용해서 participant와 completion 요소를 인덱스를 key 로 가진 맵으로 각각 만들어주고,

pMap을 탐색해서 포함되어 있지 않은 사람을 찾으려고 했다

 

이렇게 하니 효율성 테스트에서도 통과해버림~ 

근데 다른 사람의 풀이를 보니까 내가 각각 맵으로 만들어주기 전에 두 배열 모두 sort 해주었는데 

(map으로 만들 때 인덱스를 key로 넣고, 해당 key로 값을 찾아줄 때 다른 값이 나오면 completion에 포함되지 않은

사람인 것을 판단하기 위해 정렬을 해야만 했다. 정렬을 해야만 완주하지 않은 사람 제외하고 모두 같은 key 값에는

같은 value값이 들어갈테니까)

이렇게 해버리면 그냥 맵으로 만들지 않고 pariticpant 를 탐색하면서,

똑같은 방식으로 포함되어 있지 않은 사람을 찾고 그 즉시 return 해주면 되는 문제였다!

맵으로 만든 부분을 주석처리 하고 실행해보니, 역시 통과 😊

주석 처리 한 부분은 기록으로 그냥 남겨두었다 두 배열 sort 해주고 방법1, 방법2로 나눠서!

Map이나 Set 같은 자료구조는 사용할 때마다 뭔가 헷갈린다..

개발 프로젝트 할 때도 진짜 헷갈렸던 부분인데, 이 참에 한 번 짚고 넘어가게 돼서 좋았던 문제~

그리구 배열 탐색할 때 map을 자주 사용하는데, 이번과 같이 배열로 return 해줄 게 없으면 forEach를 사용하는 걸루!

2) 최종 소스코드

function solution(participant, completion) {
    let answer = '';
    participant.sort();
    completion.sort();
    
    //풀이방법1
    // let pMap=new Map();
    // let cMap=new Map();
    // participant.forEach((value,idx)=>pMap.set(idx,value));
    // completion.forEach((value,idx)=>cMap.set(idx,value));
    // for(let i=0;i<pMap.size;i++){
    //     if(pMap.get(i)!==cMap.get(i)) {
    //         answer=pMap.get(i);
    //         break;
    //     }
    // }
    // return answer;
    
    //풀이방법2
    for(let i=0;i<participant.length;i++){
        if(participant[i]!==completion[i]) {
            return participant[i];
        }
    }
}

3) 참고자료

https://inpa.tistory.com/entry/JS-%F0%9F%93%9A-%EC%9E%90%EB%A3%8C%ED%98%95-Map-%F0%9F%9A%A9-%EC%A0%95%EB%A6%AC

[JS] 📚 자바스크립트 자료형 Map 🚩 정리

https://medium.com/@hongkevin/js-5-es6-map-set-2a9ebf40f96b

[JS #5] ES6 Map(), Set()

https://bigtop.tistory.com/58

[JavaScript] 자바스크립트 forEach 메서드 이해하기