[프로그래머스](Hash) 위장 (C++)

위장 (Level 2)

문제
전체 문제 보기

코딩테스트 연습 - 위장

접근법

이 문제에서는 스파이가 가진 옷으로 서로 다른 옷의 조합의 경우의 수를 조합해 내는 것이 최종 요구사항 이다. 먼저 이 경우의 수를 어떻게 계산할 것인지 고민해 봐야한다. 입출력 예제의 첫번째 케이스를 예를 들어서 살펴보자. 우선 각 옷 종류에 따라서 스파이가 선택할 수 있는 경우의 수가 몇가지가 있는지 살펴보자.

• headgear: yellowhat을 입는 경우, green_turban을 입는 경우 총 2 개가 있다.
• eyewear: bluesunglasses을 입는 경우 1 개 가 있다.

이렇게 생각 할 수 있지만, 잘 생각해보면 해당 옷 종류를 입지 않는 경우도 존재 할 수 있다. 예를 들어서 bluesunglasses 하나만 입는 경우에는 headgear는 입지 않은것이기 때문이다. 반대로 yellowhat 하나만 입은 경우에는 eyewear를 입지 않은 것이기 때문이다. 따라서 실제로는 각각의 옷 종류에 따라서 다음과 같은 경우의 수가 존재한다.

• headgear: 아무것도 안입는 경우 / yellowhat을 입는 경우 / green_turban을 입는 경우 / 총 3 개가 있다.
• eyewear: 아무것도 안입는 경우 / bluesunglasses을 입는 경우 1 개 가 있다.

따라서 전체 경우의 수는 다음과 같다.
\[(headgear 경우의 수) \times (eyewear 경우의 수) = 3 \times 2 = 6 \]

다만 이렇게 됐을 때 한가지 문제가 있다. 바로 제한 사항에서 언급한 "스파이는 하루에 최소 한 개의 의상은 입습니다." 라는 제한 사항에 위배된다. 왜냐하면 위의 계산식에서는 headgear와 eyewear 둘다 입지 않는 경우의 수를 포함하고 있기 때문이다. 따라서 위의 수식에서 아무것도 입지 않는 경우의 수를 빼줘야 한다.

\[(headgear 경우의 수) \times (eyewear 경우의 수) - (아무것도 입지 않는 경우) = 3 \times 2 - 1= 5 \]

구현

이번에는 이 내용을 코드로 구현해볼 차례다. 이 문제는 Hash table을 사용하면 각 의상의 종류에 해당하는 의류가 몇 벌인지 쉽게 정리할 수 있다. 그래서 다음과 같이 구현한다.

• answer를 1로 초기화 한다. (뒤에서 누적 합산이 아니라 누적 곱을 할 것이기 때문에 1에서 시작해야한다.)
• 해시테이블 ht생성 (key: string(의상 종류), value: int(의상 수)) 의상 이름은 저장 할 필요가 없다.
• 동일 한 의상 종류가 들어올 때 마다 해당 의상 종류의 수량을 1씩 증가 시킨다.
• 각 의상 종류가 가지고 있는 수량에 + 1(입지 않는 경우)을 한 값을 누적으로 곱한다.
• 아무것도 입지 않는 경우에 해당하는 1을 뺀 answer을 반환한다.

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

using namespace std;

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

    // 해시 테이블 생성 (key: 옷 종류, value: 수량)
    unordered_map<string, int> ht;

    // 동일 한 옷 종류가 들어올 때 마다 ++ 
    for(auto c : clothes){
        ht[c[1]]++;
    }

    // 하나의 옷 종류의 수량 + 1을 누적 곱셈
    for(auto h : ht){
        answer *= (h.second + 1);
    }

    // 아무것도 안입는 경우를 -1
    return answer - 1;
}