[프로그래머스] 위장 C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    map<string,int> m;
    
    /* 옷의 종류 등록 */
    for(int i=0;i<clothes.size();i++)
    {
        if(m[clothes[i][1]]==0) // 처음보는 옷의 종류이면
            m[clothes[i][1]]=1; // 카운트 1로 초기화.
        else // 이미 등록된 옷의 종류이면
            m[clothes[i][1]]++; // 카운트 +1을 해줌.
    }
    
    /* 각각의 종류에 맨몸(아무것도 선택안함을 가지는 이름)이 있다고 생각하여
    **   +1하여 모든 경우의수를 계산 
    */
    int result=1;
    for(map<string,int>::iterator iter = m.begin();iter!=m.end();iter++) // 맵 탐색
        result*=(iter->second)+1; // 모든 옷의 종류를 돌며 개수+1을 result에 곱해줌
    answer=result-1; // 각각의 옷을 선택하지 않는 경우, 즉 모든것을 선택하지 않은 경우를 빼줌.
    return answer;
}

 

풀이 방법

입력을 받을 때 (이름, 종류)로 입력을 받습니다.

이때 종류를 기준으로 map에 등록합니다.

즉, 맵에 (종류, 개수)로 입력을 합니다.

 

처음 보는 종류라면 1로 초기화해 줍니다. 처음 보는 종류의 옷을 하나 찾았기 때문입니다.

이미 등록된 종류의 옷이라면 카운트 +1을 해줍니다.

 

위장을 위해 다른 옷의 조합의 개수를 계산해야 하는데.

경우의 수를 이용해 계산을 할 겁니다.

여기서 핵심 아이디어는 맨몸 즉, 아무것도 옷을 선택하지 않는 경우를 생각하여

각각의 종류에 맨몸(아무것도 선택하지 않음)을 생각하여 +1을 더하여 모든 경우의 수를 구하게

모두 곱해버립니다.

그리고 그 모든 경우의 수에 아무것도 선택하지 않는 경우(모든 종류의 옷을 선택하지 않음)를 생각하여 -1을 해

서로 다른 옷의 종류의 조합의 개수를 구할 수 있습니다.