일일코테 Day3 - 완주하지 못한 선수 - 프로그래머스 [level1]

3일째 도전도 성공. 이럴수가. 아직까지는 순조롭다.

 

문제

programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

문제는 단순하다 마라톤 참가자 명단과 완주한 선수 명단을 가지고 완주하지 못한 선수를 찾는것.

 

어떻게 완주하지 못한 선수를 찾을 수 있을까?

- 참가자 명단에서 완주한 선수들의 이름을 하나씩 지우고 마지막에 남는 참자를 완주하지 못한 선수로 본다.

- 반대로 완주한 선수 목록에서 참가자들을 하나씩 찾아가면서 참가자가 완주한 선수 목록에 없으면 그 선수를 완주하지 못한 참가자고 볼 수 있다.

첫번째 방법은 무조건 모든 선수를 다 검색해야 하는반면 두번째 방법은 참가자를 완주자 목록에서 발견하지 못하면 바로 검색을 중단 할 수 있으므로 조금 더 성능에 유리하다고 생각할 수 있다.

선수 명단에서 선수 찾기

우선 참가자 명단이건 완주한 선수 명단이건간에 둘중 하나에서 선수의 이름을 검색해야 한다. 다음과 같은 두가지 방법이 있다.

 

배열을 사용한다.

이 방법은 선수 한명 검색할때 100,000번씩 순회를 하게 되고, 복잡도는 O(N^2) 결국100k x 100k = 10M. 결국 100만번을 순회 해야 한다.                                                                                                                                                                             

 

해시맵을 사용한다.

해시맵을만들고 선수를 검색한다. 이는 해시맵을 만드는 시간이 O(N) 정도 걸리고 참가자를 검색하는 시간은 O(1)이 된다. 모든 참가자를 다 검색하는 경우 O(N)의 시간이 걸린다. 최종적으로 걸리는 시간은 2xO(N)

제약조건

참가자에는 동명이인이 있을 수 있다. 

단순히 완주자 목록에서 검색을 하게 되면 동명이인의 경우에 계속 검색이 성공하게 된다. 그래서 해시맵을 구성할때 해당 참가자의 인원수를 기록해 두고 이를 차감해 나가면서 확인해야 한다.

 

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

이는 해시키를 구성하는데 그리 일정한 상수시간의 복잡도가 소요되는것을 의미하는것 같다.

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

선수의 인원이 많기 떄문에 당연히 성능과 메모리 소비에 대해서 고민을 해봐야 한다라는 암시를 준다.

참가자의 해시맵을 구현하는데에는 20Byte x 100k = 1M byte 정도의 저장공간을 필요로 한다.

 

숨은 제약 조건으로는 참가자들이 굳이 정렬할 필요는 없다.

구현하기

function solution(participant, completion) {
    const completionMap = {};
    // init map
    for (let player of completion) {
        if (completionMap[player]) {
            completionMap[player] += 1;
        } else {
            completionMap[player] = 1;
        }
    }
    
    // search
    for (let player of participant) {
        if (completionMap[player] > 0) {
            completionMap[player] -= 1;
        } else {
            return player;
        }
    }
    
    return '';
}

구현은 간단했다. 완주자들로 맵을 구성하고, 참가자들중 완주자 목록에 있지 않는 참가자를 발견하면 그 참가자를 리턴한다.

 

다음과 같이 테스트를 통과했다.

좀 더 생각해 보기

같이 일일 1코테를 같이하는 카카오톡 단톡방에서 몇 가지 이야기를 나눴다.

 

Javascript Object 리터럴 {} 는 어떻게 구현 되어 있을까?

HashMap일까? TreeMap일까? 아래와 같은 블로그 포스팅을 찾았다.

itnext.io/v8-deep-dives-understanding-map-internals-45eb94a183df

[V8 Deep Dives] Understanding Map Internals

The Map implementation in V8 is written in C++ and then exposed to JS code. The main part of it is defined in OrderedHashTable and OrderedHashMap classes.

V8에서의 Map구현은 OrderedHashMap과 OrderedHashTable로 구현되어 있다고 한다. 아래와 같은 코드를 V8 소스코드에서 찾아볼 수 있다. 

class V8_EXPORT_PRIVATE OrderedHashMap
    : public OrderedHashTable<OrderedHashMap, 2> {
   // ...   
}

하지만 OrderedHashTable과 OrderedHashMap은 Insert와 Get을 어떻게 구현되어 있는지는 아직은 잘 모르겠다.

아래와 같은 블로그 글도 있다.

betterprogramming.pub/stop-using-objects-as-hash-maps-in-javascript-9a272e85f6a8

Stop Using Objects as Hash Maps in JavaScript

(HashMap과 TreeMap V8에서의 구현 작성중...)

 

결론은 HashMap을 사용하면 Insert와 Get의 시간의 복잡도가 O(1)이기 때문에 HashMap을 사용하는게 좀 더 성능에 유리하다.