해시(Hash) - 폰켓몬/마라톤/전화번호 목록/의상/베스트 앨범

1. 폰켓몬

최대 N/2 마리의 폰켓몬을 선택하면서, 폰켓몬 종류의 최대 개수를 구하는 문제

풀이 전략

1. 중복을 제거한 폰켓몬 종류의 개수를 구한다. (set을 사용하여 중복 제거).
2. 가능한 최대 폰켓몬 종류 수는 N/2입니다. 즉, nums에서 고를 수 있는 폰켓몬의 종류는 N/2마리입니다. 하지만 폰켓몬의 종류가 N/2보다 적으면 그 종류만큼 선택할 수 있습니다.
3. 따라서 최종적으로 고를 수 있는 폰켓몬 종류의 수는 Math.min(중복을 제거한 폰켓몬 종류의 수, N/2)이다.

알고리즘 풀이

function solution(nums) {
  // 폰켓몬의 종류를 중복 없이 셈
  const uniqueTypes = new Set(nums);

  // 선택할 수 있는 최대 폰켓몬 종류의 수는 N/2이므로, 그 값과 uniqueTypes의 크기 중 작은 값이 답
  return Math.min(uniqueTypes.size, nums.length / 2);
}

2. 마라톤

해시 테이블(또는 객체)을 사용하여, 마라톤에 참여한 선수와 완주한 선수 명단을 비교함으로써 완주하지 못한 선수를 찾는 문제

풀이 전략

1. 참가자 배열에서 각 선수의 이름을 해시 테이블에 저장
   • 각 이름을 키로 하고, 그 출현 횟수를 값으로 설정한다.
2. 완주자 배열에서 각 선수의 이름을 해시 테이블에서 찾아 카운트를 하나씩 감소:
   • 완주한 선수는 해시 테이블에서 그 출현 횟수를 감소한다.
3. 완주하지 못한 선수는 카운트가 1인 선수

알고리즘 풀이

function solution(participant, completion) {
  const map = new Map(); // 1. map 객체 생성

  // 2. 배열 순회
  for (let i = 0; i < participant.length; i++) {
    let a = participant[i],
      b = completion[i];

    map.set(a, (map.get(a) || 0) + 1); // 참가자는 + 1
    map.set(b, (map.get(b) || 0) - 1); // 완주자는 - 1
  }
  // 3. 카운트가 1인 선수 찾기
  for (let [k, v] of map) {
    if (v > 0) return k;
  }

  return "nothing";
}

3. 전화번호 목록

전화번호부에 있는 전화번호 중 하나가 다른 전화번호의 접두어인지 확인하는 문제

풀이 전략

1. 전화번호를 해시맵에 저장
   • 전화번호부의 모든 번호를 해시맵에 저장한다. 여기서 전화번호는 키로 사용되며, 값은 true로 설정한다.
2. 각 번호의 접두어 체크
   • 각 번호에 대해 접두어가 존재하는지 확인한다. 예를 들어, 번호 "12345"가 있으면 "1", "12", "123"과 같은 접두어가 다른 번호에 존재하는지 확인한다.
   • 이때, slice(0, i)를 사용하여 접두어를 추출하고, 해시맵에서 이 접두어가 존재하는지 확인합니다. 존재하면 접두어 관계가 성립되므로 false를 반환합니다.
3. 접두어가 존재하지 않으면
   • 모든 번호에 대해 접두어를 체크한 후, 접두어가 발견되지 않으면 true를 반환한다.

알고리즘 풀이

function solution(phone_book) {
  let phoneMap = new Map();

  // 1. 모든 번호 해시맵에 저장
  for (const number of phone_book) {
    phoneMap.set(number, true);
  }

  // 2. 접두어 검사
  for (const number of phone_book) {
    for (let i = 1; i < number.length; i++) {
      const prefix = number.slice(0, i);

      if (phoneMap.has(prefix)) return false; // 접두어 존재할 경우
    }
  }

  return true; // 3. 접두어가 없을 경우
}

4. 의상

주어진 의상 목록에서 가능한 옷의 조합 수를 계산하는 문제

풀이 전략

1. 의상 종류별 의상 개수 세기
   • categoryCount 객체를 해시맵으로 사용한다.
2. 각 의상 종류에서 선택 가능한 방법 계산
   • 각 의상 종류에 대해 의상을 선택하는 방법은 개수 + 1이다. 의상을 입지 않거나 해당 종류의 의상 중 하나를 고를 수 있기 때문이다.
3. 최종 가능한 조합 수 계산
   • 모든 의상 종류에 대해 가능한 조합 수를 곱해주고, 최소 1개의 의상은 입어야 하므로 마지막에 1을 빼

알고리즘 풀이

function solution(clothes) {
  // 의상의 종류별로 개수를 저장할 Map 생성
  const clothesMap = new Map();

  // 1. 의상 종류별 개수 세기
  for (const [name, type] of clothes) {
    if (clothesMap.has(type)) {
      clothesMap.set(type, clothesMap.get(type) + 1); // 해당 카테고리 의상 수 증가
    } else clothesMap.set(type, 1); // 해당 카테고리가 없으면 1로 초기화
  }

  // 가능한 조합 수 계산
  let answer = 1;
  for (const count of clothesMap.values()) {
    answer *= count + 1; // 입지 않는 경우 포함
  }

  return answer - 1; // 아무 의상도 입지 않는 경우 제외
}

5. 베스트 앨범

장르별로 가장 많이 재생된 노래를 두 개씩 선택하여 뽑는 문제

풀이 전략

1. 장르별로 곡 데이터 분류
   • genreMap이라는 Map을 사용하여 각 장르에 속하는 곡들의 데이터를 저장한다.
   • genreMap의 값은 { total: 0, songs: [] } 형태로, total은 해당 장르의 총 재생 횟수이고, songs는 해당 장르에 속한 곡들의 정보(곡 ID와 재생 횟수)를 담고 있는 배열이다.
2. 장르별 총 재생 횟수 기준으로 정렬
   • genreMap의 entries() 메서드를 사용하여 장르별로 Map 객체를 배열로 변환한 후, 각 장르의 총 재생 횟수를 기준으로 내림차순 정렬한다.
3. 각 장르에서 최대 2곡씩 선택
   • 각 장르에 대해, 해당 장르에 속한 곡들을 재생 횟수 내림차순으로 정렬하고, 재생 횟수가 같은 곡들에 대해서는 고유 번호가 낮은 곡을 우선적으로 선택한다.
   • sortedSongs.slice(0, 2)를 사용하여 각 장르에서 가장 많이 재생된 최대 2곡을 선택한다.

알고리즘 풀이

function solution(genres, plays) {
  const answer = [];
  const genreMap = new Map();

  // 장르별로 곡 데이터 분류
  genres.forEach((genre, i) => {
    if (!genreMap.has(genre)) {
      genreMap.set(genre, { total: 0, songs: [] });
    }
    genreMap.get(genre).total += plays[i];
    genreMap.get(genre).songs.push({ id: i, play: plays[i] });
  });

  // 장르별 총 재생 횟수 기준으로 정렬
  const sortedGenres = [...genreMap.entries()].sort(
    (a, b) => b[1].total - a[1].total
  );

  // 각 장르에서 최대 2곡씩 선택
  for (const [genre, { songs }] of sortedGenres) {
    const sortedSongs = songs.sort((a, b) => {
      if (b.play === a.play) {
        return a.id - b.id;
      }
      return b.play - a.play;
    });

    // 최대 두 곡 선택
    sortedSongs.slice(0, 2).forEach((song) => answer.push(song.id));
  }

  return answer;
}