[BaekJoon 9375][⚪3] 패션왕 신해빈

❓ 문제

백준 9375 - “패션왕 신해빈”

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (해시 맵 + 조합)

- 알고리즘

• Mathematics, Combinatorics, Set & Map, Hashing

- 설명

unordered_map과 조합을 사용하는 풀이이다.

옷을 카테고리별로 저장해야하므로 unordered_map의 Key로 저장하는 생각을 했고, 각 카테고리별로 중복되지 않도록 조합하는 방식을 썼다.

사실 unordered_map의 Key로 옷의 카테고리를 저장한다고 했지만, 실제 옷의 종류까지는 저장하지 않아도 된다. 왜냐하면 결국엔 서로 다른 카테고리끼리의 '조합'이기 때문에 각각의 옷의 갯수가 중요하기 때문이다. 따라서 카테고리별로 들어오는 입력값에 따라 카운팅만 해주고, 마지막에 조합식에 따라 계산을 해주면 결론이 도출된다.

각 카테고리별로 (이 카테고리에서 옷을 고르지 않는 경우 + 하나라도 고르는 경우)이기 때문에 iter->second + 1LL을 루프를 돌며 계속 곱해주고, 옷을 아예 입지 않는 경우는 제외하기 때문에 마지막에 1을 꼭 빼주면 끝이다.

unorderd_map의 삽입, 탐색은 O(1)이고 마지막에 조합 계산 루프 또한 O(N)이기 때문에 전체적인 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <unordered_map>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iT{};
    cin >> iT;

    while(iT--)
    {
        int iN{};
        cin >> iN;

        // 옷을 카테고리별로 저장할 컨테이너
        unordered_map<string, int> umapCloth{};
        umapCloth.reserve(iN);

        while(iN--)
        {
            string strName{}, strCategory{};
            cin >> strName >> strCategory;

            // 각 카테고리별로 옷 개수 카운팅
            ++umapCloth[strCategory];
        }

        long long iResult{ 1 };
        for(const auto& iter : umapCloth)
        {
            // 각 카테고리별로 (이 카테고리에서 옷을 고르지 않는 경우 + 하나라도 고른 경우) 이기 때문에 (iter.second + 1LL)이 됨
            iResult *= (iter.second + 1LL);
        }

        // -1를 해서 옷을 아예 입지 않는 경우 제외
        cout << iResult - 1 << '\n';
    }

    return 0;
}

---

💭 후기

처음엔 DP나 BFS 같은 알고리즘을 사용한 복잡한 풀이를 떠올렸는데, 단순히 조합만 하면 되는 문제인걸 깨닫고 쉽게 풀 수 있었다. 특히나 조합은 개인적으로 쉽게 간과하게 되는 부분이라서 더 그런 경향이 있던 것 같다. 항상 문제와 조건을 잘 생각하고 최적의 방안을 떠올리는 것을 연습하자.

🔗 참고자료

• 순열, 조합