개요

의상

• 문제 설명
  코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

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

  종류 이름
  얼굴 동그란 안경, 검정 선글라스
  상의 파란색 티셔츠
  하의 청바지
  겉옷 긴 코트
  코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
  착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
  코니는 하루에 최소 한 개의 의상은 입습니다.
  코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

접근 방식

첫번째 시도(시간초과)

백트래킹으로 모든 경우를 접근해보려했다.
각 재귀에서 벡터의 iterator을 넘겨주며 다음 iterator로 접근한다.
set은 두개를 사용했다.
첫번째는(kind) 현재 재귀시점에서 이미 입었던 옷의 종류를 저장하고,
두번째는(wholeKind) 지금까지 입었던 옷의 모든 조합을 저장한다.

void Search(vector<vector<string>>::iterator cursor, vector<vector<string>>::iterator end,unordered_set<string>& kind, unordered_set<string>& wholeKind,string wearingCloth) {
    if (cursor == end) return;
    if (kind.find((*cursor)[1]) != kind.end()) {
        Search(cursor + 1, end, kind, wholeKind, wearingCloth);
        return;
    }


    wearingCloth += (*cursor)[0];
    if (wholeKind.find(wearingCloth) == wholeKind.end()) wholeKind.insert(wearingCloth);
    kind.insert((*cursor)[1]);
    Search(cursor+1, end, kind, wholeKind, wearingCloth);

    wearingCloth=wearingCloth-(*cursor)[0];
    kind.erase((*cursor)[1]);
    Search(cursor+1, end, kind, wholeKind, wearingCloth);
}

백트래킹은 위코드처럼 현재 옷의 종류를 추가하고 다음 재귀를 실행시키고,
해당 재귀가 모두 끝나면 현재 옷의 종류를 제거하고 다음 재귀를 실행시켜
모든 경우를 접근하게 하였다.

string 값끼리 빼는건 연산자 재정의를 통해 b의 길이만큼 a에서 pop해줬다.

string operator-(const string& a,const string& b) {
    string tmp = a;
    for(int i=0;i<b.length();i++)
    tmp.pop_back();
    return tmp;
}

이런 식으로 접근하니 여러개의 테케가 시간초과가 났다.

두번째 시도(시간초과)

최적화하기 위해서 고민해본 결과, 현재 입는 옷들의 모든 조합을 구할 필요는 없었다.
또한 생각해보니 방문했던 경로를 다시 방문할 일이 없어서
set으로 체크를 하지 않아도 된다.

따라서, 옷의 이름의 조합을 버리고 옷의 종류의 조합만 가져가기로 했다.
옷의 종류의 조합만 구하면 각 종류에 포함된 옷들의 수만 곱하면 조합이 나온다.
예를들어 모자 a,b,c와 겉옷 d,e가 있다면
모자만 입었다면 3가지, 겉옷만 입었다면 2가지, 모자x겉옷이라면 3*2를
다 더해주면 되는것이다.

코드로 보면

void Search(map<string,int>::iterator cursor, map<string,int>::iterator end, int& answer,int combine,int tmp) {
    if (cursor == end) {
        answer += combine;
        return;
    }

    //각 태그의 
    combine *= (*cursor).second;
    Search(++cursor, end, answer,combine,tmp);
    --cursor;

    combine /= (*cursor).second;
    Search(++cursor, end, answer,combine,tmp);
    --cursor;
}

이런 느낌으로 combine변수는 초기값으로 1을 넣어준다.
따라서 각 재귀에서 해당 재귀의cursor가 가리키는 옷의 종류의 갯수만
combine변수에 곱해주고 다음 재귀로 넘어간다.
각 재귀의 cursor가 end에 닿으면 최종답인 answer에 지금까지 곱해왔던
combine변수를 더해준다.

위의 모자 겉옷의 예시를 들면,
처음에 모자 방문 combine*3, combine은 3
-> 겉옷 방문 combine*2, combine은 6
-> end iterator방문 answer+=combine, answer=6

모자 방문 후 시점으로 나와서, 겉옷 방문 안하고 end iterator방문
answer+=combine, answer =6+3

모자 방문하기 전 시점으로 나와서, 모자 방문안하고 바로 겉옷 방문
combine*2, combine= 2
-> end iterator 방문 answer+=combine, answer=6+3+2

마지막은 아무 종류도 방문안함, 바로 end iterator방문
하지만 combine은 기본값이 1이므로
answer += combine, answer=6+3+2+1

따라서 기본값1 이 더해지므로 answer에서 1을 빼야 답이 나온다.

하지만 이렇게 종류의 조합만 가지고 풀어도 1번 테스트케이스에서 시간초과가 난다.

세번째 시도 (맞음)

생각해보니 옷의 종류가 최대 갯수인 30일때 모든 케이스는
30C1+30C2 ~~~ +30C29+30C30
으로 2^30-1개로 10억개의 케이스가 넘는다.
예전에 어디서 본거로는 대충 1초에 1억의 연산을 한다고 했을 때,
10초가 넘으므로 종류가 30개일때 시간초과일거라고 생각했다.

더 이상 최적화를 못하겠어서 질문글을 봐보니 조합식을 가지고 쉽게 푸는 방식이였다..

위의 모자,겉옷 예제로 보면
모자 고를 경우의수 = (3C0+3C1) =4
3C0은 모자를 안 입었을때의 경우의수다.
겉옷 고를 경우의수 = (2C0+2C1)=3

따라서 4*3 에서 아무 옷도 안입은 경우인 1을 빼면 바로 답이나온다.

이걸 코드로 짜면

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> clothType;
    for (auto iter = clothes.begin(); iter != clothes.end(); ++iter) {
        clothType[(*iter)[1]]++;
    }
    for (auto iter = clothType.begin(); iter != clothType.end(); ++iter) {
        answer *= (1+( * iter).second);
    }
    return answer-1;
}

이런 식으로 간단하게 clotheType을 map으로 이식 후,
map을 순회하며 각 옷종류의 갯수에 1을(nC0) 더한 값을 다 곱해준 값에 -1을 하는게 답이다.

전체 코드

#include <string>
#include <vector>
#include <unordered_set>
#include <map>

using namespace std;

//조합식 이용
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> clothType;
    for (auto iter = clothes.begin(); iter != clothes.end(); ++iter) {
        clothType[(*iter)[1]]++;
    }
    for (auto iter = clothType.begin(); iter != clothType.end(); ++iter) {
        answer *= (1+( * iter).second);
    }
    return answer-1;
}

문풀후생

백트래킹이니 dp니 하는 알고리즘적 분석보다 순수하게
수학식을 사용하여 푸는게 더 효율적인 경우가 있다는 사실을 배운 문제다.

앞으로 코드를 더 최적화할때 수학을 이용해 시간을 더 줄이는 시도를 해볼것 같다. 고마운 문제