💻 위장

분류 : Hash (해시)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

해결 방안

서로 다른 옷의 조합의 수를 구하는 문제이다.
같은 종류의 옷은 못 입으며, 최소 한가지의 옷을 입어야 한다.

각 종류마다 입거나 안 입은 경우를 모두 곱해주고, 모두 안 입은 경우를 빼주면 될 것 같다.

💡 문제 풀이

방법 1 )

Algorithm의 Sort로 종류별로 정리를 하여, 경우의 수를 곱해준다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(vector<string> a, vector<string> b) {
    // 의상의 종류를 기준으로 정리해주기 위한 compare
    return a[1] < b[1];
}

int solution(vector<vector<string>> clothes) {
    int result = 1;

    // algorithm의 sort를 사용
    sort(clothes.begin(), clothes.end(), compare);

    string check_clothes = clothes[0][1];
    int clothes_combo_count = 2;	
    // 반복되는 같은 종류 체크 (2부터인 이유는 이 옷과 이 종류를 안 입은 경우)

    for (int i = 1; i < clothes.size(); i++) {
        if (check_clothes == clothes[i][1]) {
            // 이 옷이 이전 옷의 종류와 같으면 콤보 ++
            clothes_combo_count++;	
        }
        else {
            // 이 옷이 이전 옷의 종류와 다를 경우 콤보를 result에 곱해주고 초기화
            result *= clothes_combo_count;
            clothes_combo_count = 2;
            check_clothes = clothes[i][1];
        }
    }

    // 마지막으로 콤보와 곱해주기
    result *= clothes_combo_count;

    return result - 1;	// 모두 안 입은 경우를 하나 빼주고 return
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.03ms, 3.98MB)
    테스트 2 〉	통과 (0.04ms, 3.96MB)
    테스트 3 〉	통과 (0.02ms, 3.97MB)
    테스트 4 〉	통과 (0.05ms, 3.98MB)
    테스트 5 〉	통과 (0.02ms, 3.96MB)
    테스트 6 〉	통과 (0.03ms, 3.85MB)
    테스트 7 〉	통과 (0.05ms, 3.97MB)
    테스트 8 〉	통과 (0.03ms, 3.98MB)
    테스트 9 〉	통과 (0.01ms, 3.96MB)
    테스트 10 〉	통과 (0.01ms, 3.95MB)
    테스트 11 〉	통과 (0.01ms, 3.98MB)
    테스트 12 〉	통과 (0.04ms, 3.79MB)
    테스트 13 〉	통과 (0.03ms, 3.95MB)
    테스트 14 〉	통과 (0.01ms, 3.95MB)
    테스트 15 〉	통과 (0.01ms, 3.97MB)
    테스트 16 〉	통과 (0.01ms, 3.96MB)
    테스트 17 〉	통과 (0.02ms, 3.96MB)
    테스트 18 〉	통과 (0.04ms, 3.97MB)
    테스트 19 〉	통과 (0.02ms, 3.97MB)
    테스트 20 〉	통과 (0.02ms, 3.96MB)
    테스트 21 〉	통과 (0.01ms, 3.98MB)
    테스트 22 〉	통과 (0.01ms, 3.97MB)
    테스트 23 〉	통과 (0.02ms, 3.96MB)
    테스트 24 〉	통과 (0.02ms, 3.95MB)
    테스트 25 〉	통과 (0.03ms, 3.97MB)
    테스트 26 〉	통과 (0.05ms, 3.97MB)
    테스트 27 〉	통과 (0.01ms, 3.96MB)
    테스트 28 〉	통과 (0.03ms, 3.91MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n + n * log n

Sort로 의상의 종류별로 정리한 후 for 문으로 앞의 의상과 같은 종류일 경우, 의상 종류 개수를 더해주고 다른 종류일 경우 결괏값에 곱해준다.

모든 경우의 수는 그 종류를 입거나 안 입거나 이므로 모두 안 입은 경우 하나를 빼준다.

방법 2 )

Unordered_map 에 의상의 종류를 종류별로 넣어 경우의 수를 구한다.

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> clothes_map;	// {종류의 이름, 개수}
    int result = 1;

    for (int i = 0; i < clothes.size(); i++) {
        // 값을 map으로 옮겨준다. (값이 존재할 경우 ++되며, 없을 경우 추가되면서 값은 1이 된다.)
        clothes_map[clothes[i][1]]++;
    }

    for (unordered_map<string, int>::iterator iter = clothes_map.begin(); iter != clothes_map.end(); iter++) {
        // iterator로 돌면서 (종류의 갯수 + 안 입은 경우 1)을 result에 곱해준다.
        result *= iter->second + 1;
    }

    return result - 1;	// 모두 안 입은 경우를 하나 빼주고 return
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.02ms, 3.98MB)
    테스트 2 〉	통과 (0.02ms, 3.95MB)
    테스트 3 〉	통과 (0.01ms, 3.96MB)
    테스트 4 〉	통과 (0.02ms, 3.98MB)
    테스트 5 〉	통과 (0.01ms, 3.97MB)
    테스트 6 〉	통과 (0.01ms, 3.96MB)
    테스트 7 〉	통과 (0.02ms, 3.92MB)
    테스트 8 〉	통과 (0.01ms, 3.97MB)
    테스트 9 〉	통과 (0.01ms, 3.73MB)
    테스트 10 〉	통과 (0.01ms, 3.96MB)
    테스트 11 〉	통과 (0.01ms, 3.97MB)
    테스트 12 〉	통과 (0.02ms, 3.98MB)
    테스트 13 〉	통과 (0.02ms, 3.98MB)
    테스트 14 〉	통과 (0.01ms, 3.97MB)
    테스트 15 〉	통과 (0.01ms, 3.96MB)
    테스트 16 〉	통과 (0.01ms, 3.97MB)
    테스트 17 〉	통과 (0.01ms, 3.96MB)
    테스트 18 〉	통과 (0.01ms, 3.96MB)
    테스트 19 〉	통과 (0.02ms, 3.99MB)
    테스트 20 〉	통과 (0.01ms, 3.96MB)
    테스트 21 〉	통과 (0.01ms, 3.98MB)
    테스트 22 〉	통과 (0.01ms, 3.96MB)
    테스트 23 〉	통과 (0.01ms, 3.97MB)
    테스트 24 〉	통과 (0.02ms, 3.95MB)
    테스트 25 〉	통과 (0.01ms, 3.92MB)
    테스트 26 〉	통과 (0.02ms, 3.96MB)
    테스트 27 〉	통과 (0.01ms, 3.97MB)
    테스트 28 〉	통과 (0.02ms, 3.97MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n

unordered map에 종류 개수를 넣어 종류별로 곱한 후 모두 안 입은 경우 하나를 빼준다.
따로 정렬을 할 필요가 없기 때문에 방법 1보다 더 빠르다.