https://programmers.co.kr/learn/courses/30/lessons/42578
해당 문제는 해시 문제로 STL 라이브러리의 map을 통해 문제를 해결하였다.
의상 분류에 맞게 의상 개수를 증가 시키고 해당 분류의 조합으로 구성할 수 있는 의상 개수를 구하면 된다.
이 때 0(안입음) ~ 개수 중에서 몇 번 의상을 입을 것인 지를 고려하면 된다.
즉, 해당 의상 종류의 개수 +1 * 해당 의상 종류의 개수 +1 * ...
이런식으로 끝까지 곱한다음 0000....00 의 아무것도 입지 않은 경우의 수 1개만 빼주면 된다.
#include <string>
#include <vector>
#include <map>
using namespace std;
int solution(vector<vector<string>> clothes) {
map<string, int> mp;
// 입력하기
for(int i=0;i<clothes.size();i++){
auto search = mp.find(clothes[i][1]); // 찾기
if(search != mp.end())
search->second +=1;
else
mp.insert(pair<string,int>(clothes[i][1],1));
}
// 1개 일 경우 예외 처리
if(mp.size()==1)
for(auto search : mp)
return search.second;
// 그 외 조합하기
int answer = 1;
for(auto search : mp)
answer *= (search.second+1); // 각 조합 0~해당개수
answer--; // 모두 입지 않았을 경우 제외
return answer;
}
'Archived(CSE Programming) > 알고리즘(C++)' 카테고리의 다른 글
프로그래머스_프린터 (0) | 2019.11.19 |
---|---|
프로그래머스_베스트앨범(해시) (0) | 2019.11.18 |
프로그래머스_전화번호 목록(해시) (0) | 2019.11.18 |
프로그래머스_카펫 (0) | 2019.11.18 |
프로그래머스_구명보트 (0) | 2019.11.18 |