프로그래머스 코딩테스트 Kit 해시 문제풀이

프로그래머스 코딩테스트 kit에 해시로 분류되어 있는 완주하지 못한 선수, 전화번호 목록, 위장, 베스트앨범 문제풀이.

 

1. 완주하지 못한 선수

입력값

• participant: 마라톤에 참여한 선수들의 이름이 담긴 배열.
• completion: 마라톤을 완주한 선수들의 이름이 담긴 배열.

출력값

• 완주하지 못한 선수의 이름을 반환하라.

제한사항

• 1 <= participant.length <= 100,000
• completion는 participant에 비해 길이가 1개 작다.
• 참가자의 이름은 알파벳 소문자로 이루어져 있다.
• 1 <= 참가자의 이름 <= 20
• 참가자 중에는 동명이인이 있을 수 있다.

문제풀이

1. finish라는 변수명의 해쉬 맵에 completion에 있는 마라톤을 완주한 사람의 이름을 추가한다. 동명이인이 존재할 수 있기 때문에 집합이 아닌 해쉬맵을 사용하여 이름 별 빈도수를 저장한다. 

2. particapant의 길이는 completion에 비해 길이가 한상 1만큼 더 크기 때문에 finish에 저장되어있으면   

function solution(participant, completion) {
    const finish = new Map()
    for (const x of completion) {
        finish.set(x, (finish.has(x) ? finish.get(x) + 1 : 1))
    }
    return participant.filter(x => {
        if (finish.has(x) && finish.get(x)) {
            finish.set(x, finish.get(x) - 1)
            return false
        }
        return true;
    }).pop()
}

 

 

2. 전화번호 목록

 

def solution(phone_book):
    trie = {}
    for nums in phone_book:
        curr = trie
        for n in nums:
            if n not in curr:
                curr[n] = {}
            curr = curr[n]
            if '.' in curr:
                return False
        else:
            if len(curr):
                return False
            curr['.'] = {}
    return True

 

3. 위장

function solution(clothes) {
    const cnts = new Map()
    for (const [_, category] of clothes) {
        cnts.set(category, (cnts.has(category) ? cnts.get(category) + 1 : 1))
    }
    return [...cnts.values()].reduce((acc, cur) => acc === 0 ? cur + 1 : (cur + 1) * acc, 0) - 1
}

 

4. 베스트앨범

 

function solution(genres, plays) {
    const nums = new Map()
    const ids = new Map()
    for (const i in genres) {
        if (nums.has(genres[i])) {
            ids.get(genres[i]).push(i)
            nums.set(genres[i], nums.get(genres[i]) + plays[i])
        } else {
            ids.set(genres[i], [i])
            nums.set(genres[i], plays[i])
        }
    }
    const keys = [...nums.keys()].sort((a, b) => nums.get(a) < nums.get(b) ? 1 : -1)
    const result = []
    for (const key of keys) {
        ids.get(key).sort((a, b) => {
            if (plays[a] === plays[b]) {
                return a < b ? 1 : -1
            }
            return plays[a] > plays[b] ? 1 : -1
        })
        result.push(ids.get(key).pop() * 1)
        if (ids.get(key).length) {
            result.push(ids.get(key).pop() * 1)
        }
    }
    return result
}