프로그래머스에 코딩테스트 연습 중 하나인 해시 이론을 기록해보겠따!

해시

key: value형태로 갖는 하나의 자료구조
전화번호부같이 이름: 전번 같이 key를 부르면 그 값이 나오는 것!

• ⭐️원래는 for문으로 돌려서 막 검색해서 해야하는데 그러면 시간복잡도가 O(n)이므로 탐색할 수량이 많아지면 많아질수록 오래 걸린다.
• 해시는 편리하게 key만 입력해도 값이 나오도록 한 것이다. 그러면 시간복잡도 면에서 O(1)이기에 빠르고 편하다. JS에선 Object, map, set 등이 있다. 이번 기회에 배워보자
• 핵심을 통해 우리는 딱 하나의 조건을 받으면 사용 가능한데 ⭐️바로 String을 기반으로 정보를 기록하고 관리해야할때 써야한다!

예시

프로그래머스에서 가져오는 문제들

완주하지 못한 선수

기존 답

function solution(participant, completion) {
  // 이중 for문 실패 시간복잡도
  // 고차함수 find
  // 객체로 다 더해서 중복 되면 2, 중복 안되면 1 그래서 1만 나오게?? + reduce
  // return participant.find((pre) => completion.includes(pre) !== true);
  // 초기코드el
  // for (let i = 0; i < completion.length; i++) {
  //   for (let b = 0; b < participant.length; b++) {
  //     if (completion[i] === participant[b]) {
  //       participant.splice(b, 1)
  //       break;
  //     }
  //   }
  //   return participant.join('');
  // }
  participant.sort();
  completion.sort();
  return participant.find((pre, idx) => pre !== completion[idx]);
}

• 미리 한번 풀어봣던 문제다. 이중 for문은 시간복잡도가 O(n²)이라 런타임 오류가 났었다.
• 내가 풀었던 답은 sort로 먼저 굴려준다.(sort는 O(N log N)) 이름순으로 먼저 매치해준 다음 find로 해줬다. 사실 야매고 해시는 쓰지도 않았다. 이번 기회에 해보자

해시 쓴 답

1. 선수 이름이 String이고 완주 여부를 통해 기록해야하니 해시를 써야겠다고 판단(객체데이터 자체를 써도 무방)
2. 선수이름: 불린 이렇게 관리하면 되겠다. 생각

function solution(participant, completion) {
  // 3. 해시를 이용한 map
  const map = new Map();

  for (let i = 0; i < participant.length; i++) {
    let iPart = participant[i],
      iComp = completion[i];
    map.set(iPart, (map.get(iPart) || 0) + 1);
    map.set(iComp, (map.get(iComp) || 0) - 1);
  }
  for (let [a, b] of map) {
    if (b > 0) {
      return a;
    } 
  }
  return undefined;
}

• map을 이용해 해시로 처리, 훨씬 성능이 좋음!
• 포인트: || 논리 연산자로 있으면 밸류가 나오게, 아니면 0 하고 1 더하고 빼서 동명이인을 걸러줬다.

위장

위장도 String 타입의 '데이터들을 기록'하고 횟수를 구한다음 입는 종류만큼 조합을 구하기 위해 곱해야하는 구조이기에 해시구조를 이용해 구하자.
우선 난 map을 썼지만 object로도 간편하게 할 수 있다.

map 활용

function solution(clothes) {
  /*
   * 1. 형태가 map 모양이므로 걍 map에 넣어줘 활용
   * 2. map에 values을 해와 map iterator를 도출하고 from으로 배열 만들기
   * 3. 새 map에 종류 별로 몇개 있는지 넣기
   * 4. 방정식 사용, 곱해서 결과 도출
   *   4-1. 그냥 개수가 아닌 (개수+1)을 곱해주는 이유는 각 요소마다 안입는 경우의 수도 존재하기에
   *   4-2. 하나도 안입는 건 안치기에 -1 꼭 해주기
   */

  // 1
  const clothesMap = new Map(clothes);
  // 2
  const kindArr = Array.from(clothesMap.values());
  // 3
  const kindMap = new Map();
  for (let i = 0; i < kindArr.length; i++) {
    kindMap.set(kindArr[i], (kindMap.get(kindArr[i]) || 0) + 1);
  }
  // 4
  let result = 1;
  for (count of kindMap.values()) {
    result *= count + 1;
  }
  // 4-1
  return result - 1;
}

Object 활용

function solution(clothes) {
  const obj = {};
  for(let i = 0; i < clothes.length; i++) {
    const arr = clothes[i];
    obj[arr[1]] = (obj[arr[1]] || 0) + 1;
  }
  for(let key in obj) {
    result *= (obj[key]+1);
  }
  return result - 1;
}

오히려,, 기본적인 객체 데이터를 활용한 게 훨씬 보기 좋다.. 갇히지 말자

베스트앨범

/*
 * 1. 자료 만들기
 *   1-1. 해시 기록: 장르, 기록횟수, 고유번호(인덱스)
 *   1-2. 해시 기록: 장르별 듣는 횟수 기록하고 내림차순 정렬하기
 * 2. 2번의 첫 순서의 장르와 같은 객체(1번)를 새 배열로 넣고 또 내림차순 정렬
 * 3. 정렬한 걸 가지고 result에 2개씩 넣어주기
 */
function solution(genres, plays) {
  // 1-1
  const allRecord = genres.map((el, idx) => ({ genre: el, playCount: plays[idx], unique: idx }));
  // 1-2
  // const countMap = new Map();
  // for (let i = 0; i < genres.length; i++) {
  //   const genre = genres[i];
  //   const play = plays[i];
  //   // countMap.set(genre, (countMap.get(genre) || 0) + play);
  //   countMap.set(genre, countMap.get(genre) ? countMap.get(genre) + play : play);
  // }
  const countObj = {};
  for (let i = 0; i < genres.length; i++) {
    const genre = genres[i];
    const play = plays[i];
    countObj[genre] = (countObj[genre] || 0) + play;
  }
  const objToArr = Object.entries(countObj);
  objToArr.sort((a, b) => b[1] - a[1]);
  // 2
  const result = [];
  objToArr.forEach((el) => {
    let bestGenre = [];
    for (let j = 0; j < allRecord.length; j++) {
      if (el[0] === allRecord[j].genre) {
        bestGenre.push(allRecord[j]);
      }
    }
    bestGenre.sort((a, b) => b.playCount - a.playCount);
    // 3
    /* 런타임 에러
     * for (let z = 0; z < 2; z++) {
     *   result.push(bestGenre[z].unique);
     * }
     */
    bestGenre.forEach((el, idx) => {
      if (idx < 2) {
        result.push(el.unique);
      }
    });
  });
  return result;
}