[프로그래머스/C++] 위장

(6/23 - 세모)

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

코딩테스트 연습 - 위장

 

 

처음에 set과 재귀를 이용해서 순서가 없는 조합을 구하며 풀었는데, 계속 시간 초과가 떴다. 모든 경우의 수를 재귀로 다 따지고 들어가서 구하니까 시간 초과가 떠 버리지.. 알고 보니 해법이 엄청 간단했다.

 

구현

안경인 안A, 안B가 있고, 모자 모A, 모B, 모C가 있다고 치자. 이때 나올 수 있는 경우의 수는 3 * 4이다.

아무것도 안 입은 경우, 안A, 안A모A, 안A모B, 안A모C, 안B, 안B모A, 안B모B, 안B모C, 모A, 모B, 모C. 이렇게. 쉽게 말하면 해당 종류의 옷을 안 입는 경우도 같이 세어 주면 된다. 문제 조건 중에 아무것도 안 입는 경우는 없다고 했으니 -1 해 주면 된다.

해싱이 가능한 map을 이용해서 m[안경]=안A, 이런 식으로 저장한다.

 

 

코드

// 프로그래머스 고득점 Kit - 위장
#include <string>
#include <vector>
#include <map>
using namespace std;

map<string, string> m;
map<string, int> cnt;
int solution(vector<vector<string>> clothes) {
    int answer = 1;

    // 0:name 1:type
    for (auto& i : clothes) {
        m.insert({ i[0], i[1] });
        cnt.insert({ i[1], 1 });
    }

    for (auto& i : m) {
        cnt[i.second]++;
    }


    for (auto& i : cnt) {
        answer *= i.second;
    }

    answer--;
    return answer;
}

int main() {
    vector<vector<string>> c(3);
    //c[0].push_back("yellowhat");
    //c[0].push_back("headgear");
    //c[1].push_back("bluesunglasses");
    //c[1].push_back("eyewear");
    //c[2].push_back("green_turban");
    //c[2].push_back("headgear");

    c[0].push_back("aa");
    c[0].push_back("A");
    c[1].push_back("bb");
    c[1].push_back("B");
    c[2].push_back("cc");
    c[2].push_back("C");

    //c[0].push_back("yellowhat");
    //c[0].push_back("headgear");
    //c[1].push_back("bluehat");
    //c[1].push_back("headgear");
    //c[2].push_back("green_turban");
    //c[2].push_back("headgear");

    solution(c);
}