Algorithm | 위장 (해시, 해시 테이블)

프로그래머스 Lv2

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한 조건

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

예시

📍 첫번째 시도

function solution(clothes) {
    let result = 1;
    let categories = {}
    for(let idx of clothes){
        categories[idx[1]] = categories[idx[1]]? categories[idx[1]]+1 : 1;
    }
    for(let key in categories ){
        result*=categories[key];
    }
    return result + clothes.length ;
}

• 옷을 조합하여 입는 경우의 수를 구하기 위해서 =>
  "categories"에 "clothes"로 주어진 것들의 카테고리에 따라서 몇개가 들어가있는지 분류 후에
  분류된 카테고리별 갯수 즉, categories객체의 value들을 곱하였다.

• 한번에 단 하나만을 착용하는 경우 =>
  한번에 단 하나씩만 입는 경우는 categories객체의 value들의 합과 같기 때문에 이를 위에서 구한 경우의 수에 더하여 리턴하였다.

❗️ 문제점

1. 경우의 수를 구할 때 더하는 것(return 하는 부분)은 관련 없는 즉, 별개로 일어나는 경우의 수 일때에 더할 수 있다.
   ex) (3의 배수가 나올 확률) + (7의 배수가 나올 확률)

하지만 이 문제에서는 모두 한번에 조합될 수 있는 경우의 수를 찾는 문제이기 때문에 더하면 안되었다.

2. "옷을 조합하여 입는 경우의 수"를 구할때에 옷을 "입는" > [["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]경우의 수만을 구하였지, 해당하는 옷을 입지않는 경우의 수는 구해지지 않았다.

3. 제한조건인 "스파이는 하루에 최소 한 개의 의상은 입습니다."를 고려하지 않았다.

📍 두번째 시도

function solution(clothes) {
    let answer = 1;
    let categories ={};
    // 각 카테고리별 개수
    for(let idx of clothes){
        categories[idx[1]] = categories[idx[1]]? categories[idx[1]]+1 : 1; 
    }
    // 각 카테고리별 입거나 안입는 모든 경우의 수(모든 조합의 수)
    for(let key in categories){
        answer *= categories[key]+1;
    }
    // 모든 경우의 수(모든 조합의 수) - 모든 카테고리를 입지 않는 경우의 수(= 1)
    return answer -1;
}

⇨ clothes가
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]
라면,
⇨ categories는 {headgear: 2, eyewear: 1}가 되고,
⇨ 각 카테고리 별 입거나 안입는(+1) 모든 경우의 수 를 구하고(모두 입지않는 경우도 포함)
⇨ 모든 경우의 수 - 모든 카테고리를 입지 않는 경우의 수 1

해시 테이블

• 특징
  • 해시 테이블은 고정된 크기의 자료 구조로 처음에 크기가 정해진다.
  • 자료를 쉽고 빠르게 저장할 수 있다
  • 키-값 쌍을 기반으로 자료를 얻을 수 있다.
  • JS의 객체는 해시 테이블과 같은 방식으로 키(속성)와 해당 키의 연관된 값을 정의하는 방식으로 동작.

자료를 찾아보다가 이 알고리즘 문제는 해시 테이블을 사용하여 푸는 문제라고 한다. 객체와 해시테이블이 같은 방식으로 동작하기 때문에 그런 것 같다. => 곧 다시 정리할 것!

➡️ 항상 문제를 쉽게 보고 푸는 것 같다....주의깊게 생각해보고 코드를 작성할 것!