문제이해

문자열 배열 participantcompletion이 입력으로 들어옵니다.

각각 마라톤 참가한 사람들의 명단, 마라톤을 완주한 사람들의 명단입니다.

완주하지 못한 사람을 리턴하는 문제입니다.

로직

참가한 사람들의 명단을 순차 탐색합니다. 최대 10만이기 때문에 문제없습니다.
참가한 사람들을 map에 key:value이름:1대응되게 저장합니다. 이는 완주한 사람들을 이름을 인덱스로 하여 찾기 위함입니다.

완주한 사람들의 이름을 map에서 찾아서 존재하면 value값을 -1 해줍니다.

다시 map에 저장된 데이터들을 순차탐색하면서 value값이 1 이상인 경우에는 완주하지 못한 사람으로 정합니다.

기타

문제풀이보다 애매하게 넘어갔던 개념을 짚고 넘어가려고합니다.

바로 javascript Object vs ES6 Map

제가 궁금했던 부분은 time complexity of acesss by index 였습니다.

결과적으로는 차이가 없어요. Object도 hash로 동작한다네요.

code

Object를 사용한 풀이입니다.

function solution(participants, completions) {
    var answer = '';


    const obj = {};
    for(const participant of participants){
        if(!obj[participant]){
            obj[participant] = 1;
        }else{
            obj[participant] += 1;
        }
    }

    for(const completion of completions){
        if(obj[completion]){
            obj[completion] -=1;
        }
    }

    for(const participant of participants){
        if(obj[participant] >= 1){
            answer = participant;
        }
    }

효율성 테스트

image.png

Map을 사용한 풀이입니다.

    const myMap = new Map();

    for ( const participant of participants){
        if(!myMap.get(participant)){
            myMap.set(participant, 1);
        }else{
            myMap.set(participant, myMap.get(participant)+1);
        }
    }

    for(const completion of completions){
        if(myMap.get(completion)){
            myMap.set(completion, myMap.get(completion)-1);
        }
    }

    for(const participant of participants){
        if(myMap.get(participant) && myMap.get(participant) >=1 ){
            answer = participant;
        }
    }

효율성 테스트

image.png

Object vs ES6 Map 별 차이가 없습니다.Map은 hash가 떠오르죠.
순차탐색 노~! 임의접근으로 바로 액세스 하겠다는 것인데요.

C++를 사용할때는 많은 자료를 저장할때는 배열을 쓰는 경우가 많았는데요.
배열의 경우 인덱스가 정수잖아요. 인덱스가 문자열일때 배열처럼 인덱스로 바로 접근하고 싶을때 Map을 썼거든요.
인덱스로 접근하는게 훨씬 빠르잖아요.

영어가 확실치 않습니다. 검색력도 좋지는 않습니다. 다만 집단지성의 힘을 믿고
stackoverflow에 달린 답변을 보면 Object도 hash래요. 접근속도가 빠르다는 내용입니다.

오늘은 여기까지...

부족한 식견이기 때문에 틀린내용이 있을 수 있으니 꼭 정정해주세요~

레퍼런스 : Complexity of accessing data in an object - stackoverflow