https://programmers.co.kr/learn/courses/30/lessons/42578
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes)
{
int answer = 1;
//clothe, count
std::unordered_map<string, int> clotheTypeCount;
for (const auto &clothe : clothes)
{
++clotheTypeCount[clothe[1]];
}
for (const auto &clothe : clotheTypeCount)
{
//include the case that the spy does not wear this clothe
answer *= (std::get<1>(clothe) + 1);
}
//at least one clothe is needed.
return answer - 1;
}이 문제는 코딩테스트연습에 해시 카테고리에 있는 Level2 문제인데, 사실 내 기준으로 해시문제들은 대부분 map을 이용하면 풀리는 문제더라. 직접 해시화 시키라는건 아닐테고 아마... 덕분에 평소에는 별로 쓸일이 없는 unordered_map 같은 컨데이너도 연습할 기회가 있다. unordered_map과 map의 차이는 뭐, 정렬을한다 넣고뺄때 걸리는시간 등등 차이가 있는데 최소 알고리즘 문제에서는 보통은 unordered_map을 쓰면 되는것 같다.
문제는 간단히 설명하자면 스파이의 옷들이 주어질때 나올 수 있는 옷들의 조합을 구하는문제다. 코딩적으로는 그렇게 어려워보이는건 없어보이고 오히려 조합갯수를 어떻게 구할지에대해 고민해야하는 문제였던 것 같다. 결론적으로 나는 옷종류당갯수 + 그옷종류안입을경우(1) 해서 쭉 각 옷종류들의 조합을 곱한뒤 마지막에 아무것도안입었을경우(1) 을 빼주었다. 스파이는 무조건 한종류의 옷은 입어야함으로.
Programmer