[프로그래머스] 위장 - 해시 Level 2

문제 설명

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

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

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

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

제한사항

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

입출력 예

종류	이름
[[“yellow_hat”, “headgear”], [“blue_sunglasses”, “eyewear”], [“green_turban”, “headgear”]]	5
[[“crow_mask”, “face”], [“blue_sunglasses”, “face”], [“smoky_makeup”, “face”]]	3

입출력 예 설명

예제 #1 headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2 face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

알고리즘

해시: Key-value쌍으로 데이터를 저장하는 자료구조

접근 방식 및 풀이

이 문제는 의상 조합의 경우의 수를 구하는 문제이다. 기본적으로 각 부위 별로 의상을 골라서 조합하는 경우의 수는 (A1에 해당하는 의상의 개수 N1) x (A2에 해당하는 의상의 개수 N2) x … x (An에 해당하는 의상의 개수 Nn)와 같은 방법으로 구한다. 하지만 이 문제에서는 각 부위에 꼭 의상을 입어야하는 것은 아니기 때문에 의상을 선택하지 않는 경우를 의상의 종류마다 더해야 한다(+1). 또한 한가지 더 고려해야할 문제가 있다. 의상을 하나라도 입어야하기 때문에 최종 경우의 수에서 모든 의상을 입지 않은 경우는 빼야한다(-1).

위와 같은 방법을 코드로 구현해보자. 우선 의상들을 정렬한다. 정렬은 의상 종류의 알파벳 순서를 기준으로 한다. 이렇게 하면 의상 종류 별로 의상이 모이게 된다.

정렬 후, 맨 앞 의상부터 하나씩 확인한다. 만약 현재 확인하는 의상의 종류가 이전과 같으면 해당 의상 종류의 카운트를 하나 늘려주고, 이전과 다르면 새로운 의상 종류가 나온 것이기 때문에 이전 숫자는 배열에 저장해두고 새로 카운트한다.

이렇게 모든 의상들을 확인이 끝나면, 저장한 숫자들에 1씩 더해서 모두 곱한다. 마지막으로 이 값에서 1을 빼면 해당 값이 서로 다른 옷의 조합의 수가 된다.

코드

문제 풀이에 사용한 언어: 자바스크립트(JavaScript)

function solution(clothes) {
    var answer = 1;
    var count = Array(clothes.length).fill(0);
    var cur = 0;
    
		// 의상 종류를 기준으로 정렬하는 함수
    clothes.sort(function(a,b) {
        if (a[1] === b[1]) {
            return 0;
        }
        else {
            return (a[1] < b[1]) ? -1 : 1;
        }
    });
    
    count[cur]++;
    for(var i = 1; i < clothes.length; i++){
        if(clothes[i - 1][1] != clothes[i][1]) // 현재 의상과 이전 의상의 종류가 다르다면
            cur++; // 새로 카운트하기 위해 배열 한 칸 이동
        count[cur]++; // 해당 종류의 의상 개수를 늘린다
    }
    for(var i = 0; i <= cur; i++){
        answer *= (count[i] + 1); // 해당 종류의 의상을 선택하지 않는 경우를 포함하여 계산 (+1)
    }
    
    return answer - 1; // 모든 의상을 입지 않은 경우를 제외 (-1)
}