문제

Programmers, 의상

핵심

• 의상의 수 30, 의상의 종류는 1이상 20이하의 알파벳 소문자, '_'로 이루어져 있다. 의상의 종류가 의상의 수를 넘을 수 없으므로 입력 범위는 한정적이고, 구현에 초점을 맞춘다.
• 해빈이가 입을 수 있는 옷들의 조합을 구해야 한다. 의상의 종류가 다르면 겹쳐 입을 수 있으므로 이는 해빈이가 매번 옷을 입거나, 안 입는 걸 선택할 수 있는 조합 문제이다.
• 의상의 종류를 파악해야 하고, 해당 의상이 몇 개 있는지도 알아야 하기에 해시 자료구조인 map을 사용한다. 최소한 하나 이상 의상을 입은 경우의 수를 구하라 했으므로 전체 경우의 수에서 알몸인 경우(모두 선택하지 않은 경우)를 차감하여 구할 수 있다.
• 백준에 똑같은 문제가 있다.
  BOJ 9375, 패션왕 신해빈 [C++, Java]

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> m;
    for (auto& cloth : clothes)
    	m[cloth[1]]++;
    int answer = 1;
    for (auto e : m) {
        answer *= e.second + 1;
    }
    return answer - 1; 
}

Java

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> hm = new HashMap<>();
        for (var cloth : clothes)
            hm.put(cloth[1], hm.getOrDefault(cloth[1], 0) + 1);
        int answer = 1;
        for (var v : hm.values())
            answer *= v + 1;
        return answer - 1;
    }
}