Lv2_[의상, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

의상

이번 문제는 경우의 수를 계산하면 비교적 쉽게 해결할 수 있습니다.

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]

예시를 표로 정리하면 

headgear	eyewear
yellow_hat	blue_sunglasses
green_turban

headgear 2개, eyewear 1개가 있습니다. 두 가지로 입는 경우 수를 구하면 2x1 = 2를 구할 수 있습니다.
하지만 의상을 입지 않는다는 선택지도 존재하기 때문에 의상 없음 항목을 추가해서 다시 표를 그려봅니다.

 

headgear	eyewear
yellow_hat	blue_sunglasses
green_turban	입지 않음
입지 않음

headgear 3개, eyewear 2개의  경우 수를 구하면 3x2 = 6를 구할 수 있습니다.

여기서 '코니는 하루에 최소 한 개의 의상은 입습니다.'  조건에 따라서 전부 입지 않는 경우 수 1건을 제외해야 합니다.

그러므로 6 - 1 = 5로 값을 구할 수 있습니다.

 

 

알고리즘

1. 옷의 종류와 개수를 저장하기 위해 2차원 벡터로 저장되어 있는 값을 map에 저장
   • (key : 종류, value : 개수; 정렬이 필요 없기 때문에 unordered_map 활용; map을 써도 무방)
   • (의상 입지 않음을 고려해서 value에 추가로 +1을 더해줌)
2. 종류의 개수를 모두 곱해준다 (경우의 수)
3. 출력된 값에 -1을 해준다 (모두 입지 않은 경우 수)

 

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    unordered_map<string, int> un_map;
    for(auto item : clothes) {
        un_map[item[1]] += 1;
    }
 
    vector<int> v;
    for(auto m : un_map) {
        answer *= (m.second + 1);
    }
    answer--;
 
    return answer;
}