4.1해시

개요

프로그래머스에는 자료구조/알고리즘 유형별로 정리해둔 문제집인 코딩테스트 고득점 Kit이 있다. 이 중 해시와 관련된 5문제를 풀어본다.

1. 완주하지 못한 선수(lv.1)

완주하지 못한 선수는 참가자 목록에는 있는데 완주자 목록에는 없는 1명을 찾아내는 문제다.

자바스크립트에서 지원하는 Map으로 frequency counter를 만들면 효율적으로 풀 수 있다. 즉, 참가자 목록에서 이름 당 몇번 등장했는지 세는 frequency counter를 만들고(동명이인이 있으니), 완주자 목록을 순회하며 frequency counter에서 차감한 후 counter가 여전히 1인 사람의 이름을 반환하면 된다.

그러면 여기서 해시는 어디에 쓰였나?라고 생각할 수 있는데, 자바스크립트에서 지원하는 Object, Map, Set가 기본적으로 해시 구조다. 참고로, Array 역시 인덱스를 문자열 키처럼 해석해서 접근하는 방식이긴 하지만 순차적 데이터라는 측면에서 인덱스 기반이고, 키 기반인 해시 테이블과는 차이가 있다.

javascript
function solution(participant, completion) {
    const map = new Map();
    
    for(const name of participant){
        map.set(name, (map.get(name) || 0) + 1);    
    }
    
    for(const name of completion){
        map.set(name, map.get(name) - 1);
    }
    for(const [name, counter] of map){
        if(counter > 0) return name;
    }   
}

2. 폰켓몬(lv.1)

폰켓몬은 문제 설명은 매우 긴데 생각해보면 그렇게 복잡하지 않은 문제다. 개인적으로는 풀어놓고도 이게 맞는건가, 내가 꼼수를 쓴건가 고심했다.

기본적으로 가장 다양하게 뽑을 수 있는건 n/2가 한계다. 여기서, 중복되는 폰켓몬의 수만큼 뽑을 수 있는 다양성이 줄어드므로 set을 활용해서 풀었다.

javascript
function solution(nums) {
    const set = new Set(nums);
    return Math.min(nums.length / 2, set.size)
}

3. 전화번호 목록(lv.2)

전화번호 목록은 문제 자체는 간단하지만 풀이는 마냥 단순하진 않다. 우선, 게으른 접근 방식인 이중 for문은 효율성 검사에서 탈락이다.

javascript
// 효율성 검사에서 탈락
function solution(pb) {
    for(let i = 0; i < pb.length; i++){
        for(let j = 1; j < pb.length; j++){
            if(i !== j && pb[j].startsWith(pb[i])) return false;
        }
    }
    return true;
}

여기서 가장 효율적인 방법은 내장된 sort를 쓰는 것이다. 자바스크립트의 Array.prototype.sort는 TimSort를 써서 O(n log n)의 시간 복잡도를 가진다. TimSort는 이미 정렬된 구간(run)을 찾고, run이 너무 짧으면 Insertion Sort로, run이 충분하면 정렬된 run들을 Merge Sort처럼 합병한다.

sort는 사전 순으로 정렬하기 때문에, 같은 숫자로 시작되는 데이터들은 인접하게 된다. 따라서 우선 정렬을 해두고, 인접한 두 요소들을 비교해 이전의 문자열이 다음 문자열의 시작 문자열이라면 false를 반환하고, 전부 순회했을 때 이런 케이스가 없다면 true를 반환하면 된다.

javascript
function solution(pb) {
    pb.sort(); 

    for (let i = 0; i < pb.length - 1; i++) {
        if (pb[i + 1].startsWith(pb[i])) {
            return false;
        }
    }
    return true;
}

다만 이 방법은 이 챕터의 주제인 해시를 활용한 방식은 아니다. 해시의 장점인 set과 has가 O(1)이라는 점을 활용하여, Map을 통해 아래와 같이 코드를 쓸 수 있다.

javascript
function solution(pb){
  const map = new Map();
  for(let num of pb){
    map.set(num, true);
  }

  for(let num of pb){
    for(let i = 1; i < num.length; i++){
      const prefix = num.slice(0, i);
      if(map.has(prefix)) return false;
    }
  }
  return true;
}

map.has()는 O(1)의 시간 복잡도를 가지기 때문에, 앞서 본 이중 for문과 비교하면 훨씬 빠르다. 좀 더 구체적인 숫자를 통해 비교해보면, 전화번호 100,000개가 주어진다고 하면 앞선 이중 for문은 100,000 ** 2, 즉 1조번의 연산을 거친다. 반면 해시를 활용한 풀이는 전화번호의 최대 길이(num.length)가 20이라고 가정하면 O(N * M), 즉 100,000 * 20 = 200만번 정도의 연산만 거치면 된다. 이는 map.has가 O(N)이 아니라 O(1)이기 때문에 가능한 것이다.

4. 의상(lv.2)

의상은 약간의 수학적 사고가 필요하다. 각 카테고리별로 해당 카테고리의 옷들 중 하나 또는 아무것도 안 입는 선택을 할 수 있으므로, 조합은 각 카테고리의 옷들 수 + 1을 모두 곱하는 것이다.

다만, 이렇게 하면 모든 옷을 안 입을 경우가 포함되므로 결과에서 그 경우의 수 1개는 빼야한다. 코드를 작성하면 아래와 같다.

javascript
function solution(clothes) {
    const map = new Map();
    for(const [name, type] of clothes){
        map.set(type, (map.get(type) || 0) + 1);
    }
    let result = 1;
    for(const count of map.values()){
        result *= (count + 1);
    }
    return result - 1;
}

5. 베스트앨범(lv.3)

베스트앨범은 3단계 문제답게 지금까지의 문제들보다 복잡하다. 다만, Map과 sort를 충분히 이해하고 있다면 시킨대로만 해도 풀리는 문제다.

많이 들은 장르순으로 세우기 위한 frequency counter용 Map과, 그렇게 줄세운 장르에서 순서대로 많이 들은 곡 제목, 그리고 인덱스 순서(동일 재생수시 인덱스 조건에 의해)를 저장할 수 있는 Map 두 개를 만들면 해결할 수 있다.

javascript
function solution(genres, plays) {
    const genreMap = new Map();
    const songMap = new Map();
    
    for(let i = 0; i < genres.length; i++){
        genreMap.set(genres[i], (genreMap.get(genres[i]) || 0) + plays[i]);
        
        if(!songMap.get(genres[i])){
            songMap.set(genres[i], []);
        }
        songMap.get(genres[i]).push({index: i, plays: plays[i]});
    }
    
    const genreSort = [...genreMap.entries()].sort((a, b) => b[1] - a[1]).map(([genre]) => genre)
    
    const result = [];
    for(const genre of genreSort){
        const songs = songMap.get(genre).sort((a, b) => {
            if(a.plays === b.plays) return a.index - b.index;
            return b.plays - a.plays;
        })
        result.push(...songs.slice(0, 2).map(song => song.index));
    }
    
    return result
}