[해시] 프로그래머스 알고리즘 Kit 문제풀이 (JS)

[Lv1] 폰켓몬

function solution(nums) {
    const map=new Map();
 
    //폰켓몬 종류 구하기
    for(const num of nums){
        map.set(num,map.get(num)+1||1)
    }
    const type=map.size

    return Math.min(type,Math.floor(nums.length/2));
}

최대한 다양한 종류의 폰켓몬을 가져가길 원하고, nums/2만큼의 폰켓몬을 가져갈 수 있기 때문에 폰켓몬 종류의 수와 nums/2중 최소값을 리턴해주면 된다.

 

 

 

🛠 Refactor

function solution(nums) {
     //폰켓몬 종류 구하기
    const set=new Set(nums);
    const type=set.size;
   

    return Math.min(type,Math.floor(nums.length/2));
}

중복되는 요소들을 처리하기때문에, set을 사용하면 좀 더 간결하다.

 

[Lv1] 완주하지 못한 선수

function solution(participant, completion) {

    const map=new Map();
    
    //participant map 생성
    for(const p of participant){
        if(!map.has(p)){
         map.set(p,1)
        }else {
            map.set(p,map.get(p)+1)
        }
 
    }
    //순회하면서 완주자 제거하기
    for(const c of completion){
        if(map.get(c)===1){
            map.delete(c);
        }else {
            map.set(c,map.get(c)-1)
        }
    }

    return map.keys().next().value
}

간단하게 참가자 기준으로 이름별 참여자수로 map을 생성하고 완주한 선수들을 제거하는식으로 문제를 해결하였다.

완주하지 못한 참가자는 무조건 1명이기 때문에, 첫번째 key를 추출하기 위해 keys().next().value를 사용한다.

정확성: 58.3 , 효율성: 41.7

 

🛠 Refactor

function solution(participant, completion) {
    const map = new Map();
    
    // completion 선수들을 해시맵에 추가
    for(const name of completion){
        map.set(name, map.has(name) ? map.get(name) + 1 : 1);
    }
    
    //participant 선수들을 해시맵에서 확인
    for(const name of participant){
        if(!map.has(name) || map.get(name)===0){
            return name;
        }else {
            map.set(name, map.get(name) - 1);
        }
    }
 
    
}

바로 lenght가 1인 key값만 리턴하면 되기 때문에, 반대로 완주자의 map을 생성하고, 참가자를 확인하면서 

has와 카운트가 0인 조건으로 걸러내서, name을 리턴하는 방식이다.

 

 

[Lv2] 전화번호 목록

 

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

 

굳이 map,set을 쓸 이유가 없을 것같아 array로 문제를 해결하였고, 이방식은 O(n^2)로 역시나 시간초과가 발생하였다.

 

function solution(phone_book) {
    phone_book.sort();
    
    for(let i=0;i<phone_book.length-1;i++){
        let prefix=phone_book[i];
        let next=phone_book[i+1];
        if(prefix===next.substring(0, prefix.length)){ 
            return false;
        }
        continue;
    }
    return true;
}

 

어떤 번호가 다른번호의 접두어이기때문에, 전화번호 목록을 순회하면서 정렬을 해놓은 상태이기때문에 무조건 접두어가 존재한다면 바로 다음 요소가 해당되는지 확인을 하면된다. 다음을 건너뛰고 다다음은 불가능하다!

그래서 substring으로 prefix 길이만큼 확인해서 같다면 리턴해주고, 같지 않다면 더 순회하면서 확인해볼 필요도 없기때문에 continue를 사용했는데 생각해보니 continue와 무관하게 동작한다

 

 

 

🛠 Refactor

function solution(phone_book) {
  return !phone_book.sort().some((v, i) => {
    if (i === phone_book.length - 1) return false; //마지막 요소

    return phone_book[i + 1].startsWith(v); //접두어 만족한다면,true
  });
}

sort하고 some메서드로 하나라도 조건을 충족하면 바로 true를 리턴하고 순회하지 않는다.

반대로 리턴해야하기때문에 !연산자를 사용해주고, startsWith메서드로 접두어 조건을 확인해준다.

 

 

✅ startWith() :boolean

특정문자열로 시작하는지 결과를 boolean으로 리턴한다.

 

 

[Lv2] 의상

function solution(clothes) {
    let answer = 1;
    //의상종류에 따른 count map 생성
    const map=new Map();
    for(const [name,type] of clothes){
        map.set(type,map.get(type)+1||1)
    }
    //각 종류별 경우의 수 구하기
    for(const values of map.values()){
        answer*=values+1;
    }
    
    return answer-1;
}

각 의상종류에 따른 코디의 경우의 수를 구하는 문제이기 때문에, 각 의상종류에 대한 카운트 map을 생성하고 , 착용하지 않는 경우를 포함해서 +1한 상태로 곱해주면된다. 리턴할때 아예 모든 의상을 착용하지 않은 경우는 제외해야하므로 -1을 뺀다.

 

[Lv3] 베스트 앨범

function solution(genres, plays) {
    var answer = [];
    //[ [ 'pop', 3100 ], [ 'classic', 1450 ] ] 
    //장르별 재생횟수 obj
    const obj={}; //{ classic: 1450, pop: 3100 }
    
    for(let i=0;i<genres.length;i++){
        const genre=genres[i];
        const playCount=plays[i];
        
        if(!obj[genre]){
            obj[genre]=playCount
        }else {
            obj[genre]+=playCount
        }
    }
    //obj Array로 변경
    const genreArray=Object.entries(obj);
    genreArray.sort((a,b)=>b[1]-a[1])
    
    
    //play, genre, index객체의 array생성
    const infoArray=genres.map((genre,index)=>({
        genre:genre,
        playCount:plays[index],
        index:index
    }))
    
    //장르별 순회하면서 2개씩 뽑기
    genreArray.forEach((array,i)=>{
        let current=[];
        for(const info of infoArray){
            if(array[0]===info.genre){
                current.push(info);
            }
        }
          //playCount 내림차순 정렬
        current.sort((a,b)=>b.playCount - a.playCount);
        current.forEach((v, i) => {
      if (i < 2) {
        answer.push(v.index);
      }
    });
        
    })
    return answer;
}

장르별 재생횟수를 카운트하고 내림차순으로 정렬해야하므로, 객체로 먼저 만들고 배열로 변경해줘야한다.

그리고 모든 정보를 가진 객체를 만들어주고, 재생횟수 순으로 정렬한뒤 각 장르별 두개씩 뽑아 결과를 리턴해야하므로

infoArray를 순회하면서 장르를 기준으로 current 배열에 넣어준뒤 재생횟수순으로 정렬하면 다음과 같다.

//current
[
  { genre: 'pop', playCount: 2500, index: 4 },
  { genre: 'pop', playCount: 600, index: 1 }
]
[
  { genre: 'classic', playCount: 800, index: 3 },
  { genre: 'classic', playCount: 500, index: 0 },
  { genre: 'classic', playCount: 150, index: 2 }
]

그리고 최종적으로 current 배열을 순회하면서 두개씩 뽑아 result 배열에 넣어준다.