[JS] 코딩테스트 고득점 Kit - 해시 한번에 정리하기

시작하면서 ...

이 글은 프로그래머스의 고득점 Kit에서 해시 파트만 따로 정리해놓는 포스트입니다. 

문제 접근 방식

1. 문제 나열 및 해석
2. 코드 작성 저도 제 방식대로 풀긴하겠지만, 더 좋은 풀이가 있다면 그걸로 정리하겠습니다.
3. 모든 문제에서 사용된 문법, 로직 총 정리

 

폰켓몬 Level 1

• 박사의 배열중 절반을 가져갈수있는데, 가져갈수있는 다른 종류의 갯수를 구해라.
  = 배열이 절반 이상 다 다르면 무조건 N/2가 답이고, 이하면 다른 갯수다.

//그냥 set에 넣은뒤에 set길이 반환하고 만약에 set길이가 크면 N/2 반환하면 될것같은뎅.

function solution(nums) {
    let maxLen = nums.length / 2;
    let set = new Set(nums);
    return set.size > maxLen ? maxLen : set.size;
}

시간복잡도: O(N)
공간복잡도: O(N)

완주하지 못한 선수 Level 1

• Input : 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion
• Output: 완주하지 못한 선수의 이름

= completion배열애서 participant배열 빼면 뭐남는지 뱉어라

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

    for(let i = 0; i < participant.length; i++) {
        let pName = participant[i];
        let cName = completion[i];
        map.set(pName, (map.get(pName) || 0) + 1);
        map.set(cName, (map.get(cName) || 0) - 1);
    }

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

    return 0;
}

 

전화번호 목록 Level 2

• input: 전화번호부에 적힌 전화번호를 담은 배열 phone_book
• output : 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return
  = 배열안에 있는 요소가 배열안에 있는 요소의 맨 앞에 달려있으면 false, 아니면 true를 뱉는 문제.

function solution(phone_book) {
    phone_book.sort();

    for (let i = 0; i < phone_book.length - 1; i++) {
        if (phone_book[i + 1].startsWith(phone_book[i])) {
            return false; // 접두어가 발견되면 false를 반환합니다.
        }
    }

    return true; // 접두어가 없으면 true를 반환합니다.
}

시간복잡도 : O(n log n + nm)

의상 Level 2

• Input: 코니가 가진 의상들이 담긴 2차원 배열 clothes
• output: 서로 다른 옷의 조합의 수
  => 확통 생각해보면 아래와 같다.

머리에 쓰는거: a개(모자, 안경, 마스크)
다리에 쓰는거: b개
발에 쓰는거: c개

일때 아무것도 안입는 경우는 없다고 가정하고, 한개씩만 착용할수있다고 할때 옷을 입는 경우의 수는 다음과 같다.

모자쓸때, 안경쓸때, 마스크쓸때, 아무것도 안쓸때(a+1) x (b + 1) x (c + 1) - 1 아무것도 안입는경우는 뺌.

function solution(clothes) {
    let map = new Map();
    for(let [name, body] of clothes){
        map.set(body, (map.get(body) || 0) + 1);
    }

    let result = 1;
    for(let count of map.values()){
        result *= (count + 1);
    }

    return result - 1;
}

베스트앨범 Level 3

• Input : 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays
  ["classic", "pop", "classic", "classic", "pop"]
[500, 600, 150, 800, 2500]
• output: 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로나타내는 배열
  [4, 1, 3, 0]

수록되는 기준

• 장르자체가 많이 재생됨
• 장르 내에서 그 노래가 많이 재생됨
• 장르내에있는 그 노래중 고유번호가 더 작음

function solution(genres, plays) {
//장르별 재생수
    var dic = {};
    genres.forEach((t,i)=> {
        dic[t] = dic[t] ?  dic[t] + plays[i] :plays[i];        
    });

    var dupDic = {};
    return genres          
          .map((t,i)=> ({genre : t, count:plays[i] , index:i}))
          .sort((a,b)=>{              
               //장르별 재생수가 다르면 그걸로 정렬(오름)
               if(a.genre !== b.genre) return dic[b.genre] - dic[a.genre];
               //재생수가 다르면 그걸로 정렬(오름)
               if(a.count !== b.count) return b.count - a.count;
               //인덱스 값이 차이나면 그걸로 정렬(내림)
               return a.index - b.index;
           })
           .filter(t=>  {
           //한 장르당 최대 2개이기때문에 장르당 갯수를 세고 2개씩 고르기
               if(dupDic[t.genre] >= 2) return false;
               dupDic[t.genre] = dupDic[t.genre] ? dupDic[t.genre]+ 1 : 1;
               return true;
            })
            //남은것중에 index만으로 이루어진 배열 만들기
           .map(t=> t.index);    
}

 

알아야하는 문법
forEach((t,i) => ....) : 배열의 각 요소에 대해 주어진 함수를 실행

• t: 현재 처리 중인 배열의 요소
• i: 현재 처리 중인 요소의 인덱스

  const fruits = ['apple', 'banana', 'cherry']; fruits.forEach((fruit, index) => { console.log(`Fruit at index ${index}: ${fruit}`); });

.map((t,i) => ....) map은 배열의 모든 요소에 대해 주어진 함수를 호출하고, 그 결과로 새로운 배열을 만듭니다.

• t: 현재 처리 중인 배열의 요소
• i: 현재 처리 중인 요소의 인덱스

  const numbers = [1, 2, 3, 4, 5]; const doubledNumbers = numbers.map((num, index) => { return num * 2; }); console.log(doubledNumbers);

.sort((a,b) => ....) sort는 배열의 요소를 정렬합니다. 비교 함수를 인자로 받아 정렬 순서를 결정합니다.

• a, b: 비교 중인 두 요소

비교 함수는 다음과 같이 동작합니다:

• b-a : 맨앞이 젤 크게
• a-b: 맨앞이 젤 작게

  const scores = [80, 100, 70, 90, 85];
  const sortedScores = scores.sort((a, b) => {
    return b - a; // 내림차순 정렬
  });