[프로그래머스/42578번/JavaScript] 위장

문제

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

 

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

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

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

제한 사항

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

입출력 예

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]	3
이 아래부터는 제가 임의로 추가한 테스트 케이스입니다.
[["yellow_hat", "headgear"], ["green_turban", "headgear"]]	2
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"], ["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	23
[["yellow_hat", "headgear"]]	1

---

서론

글을 쓰면서 이 문제의 카테고리를 어느 카테고리로 정해야 할까 고민이 많았다.

 

문제 풀이를 위해 필요한 개념은 조합이니까 수학 카테고리로 넣어야 할까? 아니면 (아래서 보겠지만) 풀이 과정에서 Map을 사용하니까 맵 카테고리에 넣어야 할까?

 

고민을 하다가 그냥 구현 카테고리에 넣었다. 사실 조합 개념을 몰라도 직관적으로 문제 풀이에 필요한 공식을 유도해낼 수 있고, 나는 풀이 과정에서 Map을 사용했지만 굳이 Map을 사용하지 않아도 되기 때문이다. 이 공식 유도 과정은 다음과 같다.

풀이에 사용할 알고리즘 구상

이 문제의 핵심은 정답(옷을 입는 모든 경우의 수)을 도출해내는 식을 알아내느냐 못하느냐에 달려있다. 따라서 문제에서 제시한 옷을 입는 모든 경우의 수를 차근차근 구해보도록 하겠다.

 

옷을 입는 모든 경우의 수를 구하기 위해서는, 옷의 종류마다 내가 선택할 수 있는 경우의 수부터 구하고, 이 수에 옷 종류의 개수를 곱해주면 된다. 옷의 종류마다 내가 선택할 수 있는 경우의 수는 (종류별로 존재하는 서로 다른 옷 개수)+1이다. 왜 +1을 하냐면, 해당 종류의 옷을 입지 않아도 되기 때문에 해당 종류의 옷을 고르지 않는 경우까지 포함해야 하기 때문이다. 단, 이렇게 경우의 수를 계산할 경우 아무 옷도 입지 않는 경우가 생기는데, 이러면 스파이는 알몸으로 위장을 하기 때문에(정확히는 스파이는 하루에 최소 한 개의 의상은 입습니다.라는 조건이 있기 때문에) 이 경우는 최종 답안에서 제외해 주어야 한다.

즉, 각 종류마다 (종류별로 존재하는 서로 다른 옷 개수)+1개의 경우의 수가 존재하기 때문에, 모든 종류마다 이 수를 구해서 전부 곱해주면 문제에서 요구하는 옷을 입는 모든 경우의 수를 구할 수 있게 된다. 단, 앞서 말한 알몸의 경우를 방지하기 위해 꼭 마지막에 1을 빼주자.

 

이 식을 가지고 문제의 첫 번째 테스트 케이스인 [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]의 입력이 들어왔을 때 출력을 구하는 과정을 나타내면 다음과 같다. 먼저 옷의 종류 headgear에는 2가지 옷 yellow_hat과 green_turban이 존재한다. 따라서 선택할 수 있는 가짓수는 3이다. 다음 종류인 eyewear에는 blue_sunglasses의 한 가지 옷만 존재하기 때문에 선택할 수 있는 가짓수는 2다. 따라서 정답은 3 * 2 - 1을 통해 구할 수 있고, 최종 정답은 5가 되는 것이다.

 

그렇다면 이제 입력받은 데이터를 경우의 수로 가공하여 푸는 방법만 알게 되면 이 문제는 끝이다. 문제에서 옷 종류는 headgear, eyewear와 같은 문자열 입력으로 주어지므로, 이를 적당히 가공하여 풀면 더 간단하게 풀 수 있을 것이다.

 

나는 그래서 Map 자료구조를 사용하기로 했다. 앞서 말한 옷의 종류를 key로 하고, 해당 옷 종류에 속하는 옷의 배열을 value로 하는 Map을 만들면 문제를 더 쉽게 풀 수 있을 것이다. 입력을 받았을 때, 해당 옷의 종류를 key로 하는 데이터가 Map에 있을 경우, 해당 key의 value에 입력받은 옷을 추가하고, 아닐 경우 value를 입력받은 옷만을 포함하는 배열로 설정하여 새 데이터를 설정하는 방식이다. 이렇게 Map을 사용한 뒤, JavaScript의 Array.from() 메소드를 사용하면 Map을 배열로 바꾸어 배열 내에 모든 옷 전부를 저장할 수 있게 되는데, 이러면 배열을 쭉 탐색하면서 Array.length를 통해 해당 옷 종류에 속하는 옷의 가짓수를 쉽게 알아낼 수 있고 이것을 전부 곱하기만 하면 되기 때문에 쉽게 사용할 수 있어서 편하고 좋다.

제출 코드

function solution(clothes) {
    let map = new Map();

      // clothes를 탐색하며 옷이 Map에 저장된 종류일 경우 value에 새 옷을 저장, 아닐 경우 value를 새 옷을 배열 형식으로 저장
    for (let clothInfo of clothes) {
        map.get(clothInfo[1]) ? map.set(clothInfo[1], map.get(clothInfo[1]).concat(clothInfo[0])) : map.set(clothInfo[1], [clothInfo[0]]);
    }

      // Map을 Array로 변환
    let arr = Array.from(map);

      // 옷 종류가 하나일 경우 해당 종류의 가짓수가 바로 정답이니 early return
    if (arr.length === 1) return arr[0][1].length;

      // 옷 종류가 여럿일 경우 배열을 순회하면서 (종류별 옷 가짓수+1)을 정답에 곱한다.
    let answer = 1;
    arr.forEach(e => {
        answer *= e[1].length+1;
    });
    return answer-1; // 최종 답안에서 1을 빼는 것 잊지 말기
}