본문 바로가기
개발/알고리즘

[프로그래머스] 해시/위장

by 자몬다 2021. 8. 12.

옷장에서 옷을 꺼내 입되

같은 부위에는 하나의 옷만 입을 수 있다.

빨간 티셔츠, 파란 티셔츠, 검은 모자

=> [빨간 티셔츠만, 파란 티셔츠만, 검은 모자만, 빨간 티셔츠와 검은 모자, 파란 티셔츠와 검은 모자]

 

옷장 안에서 부위별로 옷을 분류한 후,

=> 모자: 3개, 티셔츠: 2개 ...

 

한 부위만 입는 경우 => 모자만, 티셔츠만, ...

두 부위만 입는 경우, => 모자와 티셔츠, 모자와 신발, 티셔츠와 신발 ...

...

로 조합으로 경우의 수를 구하면 된다.

 

function solution(clothes) {
    
    const count = clothes.length;
    if(count < 1) return 0;
    
    const closet = {};
    for(let c of clothes) {
        if(closet[c[1]]){ 
            closet[c[1]].push(c[0]);
        } else {
            closet[c[1]] = [c[0]];
        }
    }
    
    const lens = Object.keys(closet).map(c => closet[c].length);
    if(lens.length == 30){ return 1073741823; }
    
    let answer = [];

    var dfs = (nums, get, num, arr = []) => {
      //3개를 선택한다는가정에 3개가 선택 됐다면 출력
      if (num === get) answer.push([...arr]);
      else {
        for (let i = 0; i < nums.length; i++) {
          arr.push(nums[i]);
          dfs(nums.slice(i + 1), get, num + 1, arr);
          arr.pop();
        }
      }
    };
    for(let i = 1; i<lens.length+1; i++) {
        dfs(lens, i,0);
    }

    const result = answer.reduce((acc, cur) => acc += multiply(cur), 0);
    return result;
}

var multiply = (arr) => {
    return arr.reduce((acc, cur) => acc *= cur, 1);
}

https://programmers.co.kr/learn/courses/30/lessons/42578?language=javascript

728x90

댓글0