[프로그래머스 알고리즘 고득점 Kit] 문제풀이 - 해시

1. 폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

1-1. 이전 내 풀이

이미 풀었던 문제였는데 Set 을 사용하여 중복을 없애고 길이를 구한 다음 nums 의 절반과 중복을 제거한 길이 중에 작은 수를 반환했다.

function solution(nums) {
    const newSet = new Set(nums);
    const result = [...newSet].length;
    const count = nums.length / 2
    return result < count ? result : count;
}

1-2. 지금 내 풀이

Map 을 사용하여 풀어보았다. 다시 생각해보니깐 Set 으로 푸는 것이 좀 더 효율적인 거 같다.

function solution(nums) {
    const table = new Map();
    
    nums.map((item)=>{
        table.set(item, true);
    })
    
    return Math.min(nums.length/2, table.size);
}

 

2. 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

2-1. 내 풀이

선수와 완주한 선수를 정렬한 후, 같이 않으면 그 선수를 리턴해 완주하지 않았음을 보여준다. 그리고 완주못한 선수가 맨 뒤로 정렬되었을 경우 그 값을 리턴해서 완주하지 않은 선수를 구했다. 그런데 다른 사람 풀이를 보니 이게 좋은 방법은 아니다

function solution(participant, completion) {
    participant.sort();
    completion.sort();
    
    for(i=0; i<completion.length; i++) {
        if (participant[i] !== completion[i]) return participant[i];
    }
    return participant.pop();
}

2-2. 다른 사람 풀이

Map 객체를 만들고, 참가자를 Map 에 집어 넣는데 만약 이미 Map 에 있으면 해당 값에 1을 더하고, 없으면 0에 1을 더했다. 그리고 완주자로 Map 에 넣을 때 -1을 뺐다. 그러면 결국 완주를 했으면 값이 0이 되었을 것이고 완주를 못 했으면 값을 빼지 못해 1이상일 것이다. 다음으로 Map 객체를 순회하여, 값이 0보다 크면 반환하여 리턴하지 못한 사람을 구했다.

function solution(participant, completion) {
    const map = new Map();

    for(let i = 0; i < participant.length; i++) {
        let a = participant[i], 
            b = completion[i];

        map.set(a, (map.get(a) || 0) + 1);
        map.set(b, (map.get(b) || 0) - 1);
    }

    for(let [k, v] of map) {
        if(v > 0) return k;
    }

    return 'nothing';
}

 

3. 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

3-1. 내 풀이

전화번호부를 문자 순서대로 정렬하였다. 그러고 바로 옆에 있는 것과 비교해서 포함된 값이 0번 인덱스(접두사)면 false 를 반환했다.

function solution(phone_book) {
    phone_book.sort();
    
    for(i=0; i<phone_book.length-1; i++) {
        if(phone_book[i+1].indexOf(phone_book[i]) === 0) return false;
    }
    return true;
}

3-2. 다른 사람 풀이

startWith 라는 것도 있었다

function solution(phoneBook) {
    return !phoneBook.sort().some((t,i)=> {
        if(i === phoneBook.length -1) return false;

        return phoneBook[i+1].startsWith(phoneBook[i]);        
    })
}

 

4. 의상

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

4-1. 내 풀이

해시라는 카테고리에 맞게 Map 으로 풀었다. 각 종류별로 안입음이라는 조건도 추가하기 위해 table.get(b) 가 없으면 1에다가 1을 더했다. 그리고 모두 안입었을 때라는 조건을 빼야하기 때문에 마지막에 1을 뺐다.

function solution(clothes) {
    const table = new Map();
    let result = 1;
    
    clothes.map(([a, b])=>{
        table.set(b, (table.get(b) || 1) + 1)
    })
    
    for(const [a,b] of table) {
        result *= b;
    }
    
    return result-1;
}

 

5. 베스트앨범

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

5-1. 내 풀이

Map 을 사용하여 각 장르별 노래 합을 구하고, songs 이라는 배열에 장르, 플레이 수, 인덱스를 배열로 만들었고, 플레이 수를 기준으로 오름차순 정렬하였다. 그리고 Map 에 들어 있는 각 장르별 노래 합을 오름차순으로 정렬하여 배열로 만들었다. 그리고 그 배열을 순회하여 장르가 같으면 그 음악의 인덱스를 결과에 넣고 cnt 를 증가 시켜 2곡까지 담기도록 했다.

function solution(genres, plays) {
    const table = new Map();
    const result = [];
    
    const songs = genres.map((item, index)=>{
        table.set(item, (table.get(item) || 0) + plays[index])
        return [item, plays[index], index]
    }).sort(([, a,], [, b,]) => b-a);
    
    const order = [...table].sort(([, a], [, b]) => b-a);
    
    order.map((item)=>{
        let cnt = 0;
        for(const music of songs) {
            if(music[0] === item[0]) {
                cnt ++;
                result.push(music[2]);
            } 
            if (cnt === 2) break;
        }
    })
    
    return result;
}