[Programmers] 의상

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

프로그래머스

 

---

 

문제 해결 과정

착안

코니가 가진 의상의 종류가 $i$ 개이고 각 종류별 의상 수를 $n_i$ 라고 하면, 종류별로 입지 않는 경우와 하나를 택해서 입는 경우가 존재할 수 있다. 이때, 모든 종류를 입지 않는 한 가지 경우를 제외하면 코니가 서로 다른 조합으로 옷을 입을 수 있는 경우의 수 $c$ 는

$$c = \prod_{i} n_{i} - 1$$

이다.

 

구현

std::vector<std::vector<std::string>> 형식으로 주어지는 매개변수로부터 각 종류별 의상의 수를 카운팅할 때, 문자열 형식의 데이터를 여러 번 비교하는 과정을 필요로 한다. 따라서 std::unordered_map<string, int> 클래스 형식의 컨테이너를 활용하면 보다 효율적으로 종류별 의상의 수를 카운팅할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes)
{
    int answer = 1;
    unordered_map<string, int> um;
    for (const vector<string>& v : clothes)
        um[v[1]]++;
    
    for (const pair<string, int> p : um)
        answer *= p.second + 1;
    
    return answer - 1;
}

 

실행 결과