[프로그래머스/알고리즘] 위장

문제 설명

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

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

종류 이름 

얼굴 동그란 안경, 검정 선글라스 

상의 파란색 티셔츠

하의 청바지 겉옷

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

해결 방법

이 문제를 해결하는 방법은 누가봐도 해시를 이용하라는 것을 대놓고 보여줍니다.

얼굴 위치에 안결과 선글라스를 저장하고, 상의에다 티셔츠를 저장하고, 하의에다 겉옷을 저장하면 됩니다.

하지만 모든 입는 경우를 일일이 나열하는 것이 아니라 단지 몇가지 있는지 개수만 물어보기 때문에

얼굴에는 2가지, 상의는 1가지, 하의는 1가지

이렇게 저장하면 더 쉽게 계산하기 쉽습니다.

얼굴, 상의, 하의를 구별해서 저장하기 위해 map을 이용하고 

그 후에 map의 value를 뽑아서 계산을 하면 됩니다.

마지막 계산과정은 현재 까지 입은 과정 수+지금까지 의상경우*다음 의상 경우+다음 의상만 입을 경우를 이용해서 구했습니다.

다른 방법으로는 경우의 수를 이용해서

얼굴은 안 입는 경우, 동그란 안경 입는 경우, 검정 선글라스 입는 경우 =3

상의는 안 입는 경우, 파란색 티셔츠 입는 경우=2

하의는 안 입는 경우, 청바지 겉옷 입는 경우=2

이 전체를 경우는 서로 독립적이기 때문에 3개를 곱하면 됩니다. 

하지만 얼굴, 상의, 하의 3개다 안 입는 경우는 없으므로 -1만 하시면 아마 답을 구하실 수 있습니다.(이거 적으면서 깨달았네요)

소스 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
void dfs(int value, int &answer, vector<int> temp, int n);
int solution(vector<vector<string>> clothes) {
	int answer = 0;
	int value = 0;
	vector<int> temp;
	map<string, int> hash;
	for (int i = 0; i < clothes.size(); i++) {
			hash[clothes[i][1]]++;		
	}
	map<string, int>::iterator ihash=hash.begin();
	answer = hash.begin()->second;
	for (ihash++; ihash != hash.end(); ++ihash) {
		answer=answer+(answer+1)*ihash->second;
	}


	return answer;
}