해시-Level2-위장(Java,C++,Python,Javascript)

설탕유령·2022년 8월 27일

[문제 설명]

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

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

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

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

[제한사항]

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

[입출력 예]

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]	3

공통로직

모든 요소를 곱해 경우의 수를 구하는 것으로 해결이 가능하다.

Python

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

Counter는 주어진 값을 분해해 각 항목을 키로 해서 나온 개수를 알려준다.
먼저 clothes를 분해해 옷의 종류를 Counter의 키로 삼는다.
결과로는 각 옷의 종류를 Key로 삼고 개수를 value로 삼게된다.
reduce()는 여러 개의 데이터를 대상으로 누적 집계를 내기 위해 사용한다.
reduce(집계 함수, 순회 가능한 데이터, 초기값)의 형태로 사용된다.
즉 초기값 1이 설정되고, cnt에 담긴 옷 종류별 개수를 기반으로 순회한다.
lambda x, y에서 x는 누적된 값, y는 현재 순회 대상 cnt.values()값이다.
x(누적값) y(종류별 옷 개수)를 곱해서 모든 경우의 수를 구할 수 있지만, 입지 않는다의 조건을 고려해야 하기 때문에 x(y+1)의 형태로 1를 추가해준다.
또한, 전부 안입는다의 경우는 불가능 하기에 마지막에 -1을 해주는 것으로 경우의 수를 구한다.

C++

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    unordered_map <string, int> attributes;
    for(int i = 0; i < clothes.size(); i++)
        attributes[clothes[i][1]]++;
    for(auto it = attributes.begin(); it != attributes.end(); it++)
        answer *= (it->second+1);
    answer--;

    return answer;
}

clothes에 대한 반복을 통해 해시 테이블에 옷의 종류를 key로 대상을 해 값을 1씩 증가켜준다.
과정이 완료되면 옷 종류를 key로 사용하고 해당 종류별로 옷의 개수가 저장된 해시 테이블이 완성된다.
만들어진 Hash를 기준으로 반복문을 진행한다.
Hash에 요소를 하나씩 꺼내어 answer라는 누적값에 현재 Hash 요소의 값을 +1해서 곱해준다.
it→second 방식으로 Hash의 Value를 참조하고, it→first로 Key를 참조할 수 있다.
반복이 끝나고 마지막으로 answer-- 를 해주는 것으로 전부 입지 않는다의 경우의 수를 제외해준다.

Java

import java.util.*;
import static java.util.stream.Collectors.*;

class Solution {
    public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
                .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting())))
                .values()
                .stream()
                .collect(reducing(1L, (x, y) -> x * (y + 1))).intValue() - 1;
    }
}

배열을 stream을 사용해 처리한다.(컬렉션의 저장 요소를 하나씩 참조해 람다식으로 처리할 수 있도록 해주는 반복자)
.collect()를 사용해 Steam 데이터의 변형 처리를 진행한다.
groupingBy를 이용해 데이터 집합을 하나 이상의 특성으로 분류, 그룹화가 가능하다.
clothes는 이름과 종류로 구성이 되어 있으며, p → p[1] 즉 옷의 종류를 기준으로 grouping이 진행된다.
의상의 종류로 grouping이 지정되고, 값을 처리할 때 mapping을 사용한다.
mapping은 요소를 다른 값으로 변화시키는데, 이번에 그 대상은 countring()으로 계산된 수로 반환이 된다.)
처리가 된 collect을 values()를 이용해 값을 추출해 오고, 다시 stream(), collect()를 통해 내부 요소에 대한 연산을 기작한다.
reducing를 통해 누적값 x에 현재 요소 y를 이용해 경우의 수를 계산해준다.
(파이썬과 동일한 방법)

Javascript

function solution(clothes) {
    return Object.values(clothes.reduce((obj, t)=> {
        obj[t[1]] = obj[t[1]] ? obj[t[1]] + 1 : 1;
        return obj;
    } , {})).reduce((a,b)=> a*(b+1), 1)-1;    
}

먼저 reduce()를 이용해 clothes에 대한 전처리를 해준다.
누적값인 obj는 객체로, 현재값 t[1] 즉 현재 옷의 종류를 누적값 obj의 key로 활용해준다.
만약 obj[t[1]] ? 즉 현재 옷 종류를 key로 삼는 값이 이미 존재한다면, 현재 값에 +1을 해주고, 아니면 초기 값을 1로 넣어준다.
reduce 이후 반환되는 객체를 Object.values로 갑싸 객체 내부에 값(종류별 개수)만 추출해준다.
추출된 개수는 reduce 함수를 이용해 다시한번 경우의 수 연산을 진행하고 마지막에 -1을 통해 반환해준다.