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

 

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

코딩테스트 연습 - 위장

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

 

해당 문제 또한 DFS 알고리즘으로 풀이했다가 

테스트 CASE 1을 시간초과로 통과하지 못함.

그래서 머리 초기화 하고 다시 풀어서 통과함.

 

그 동안 너무 알고리즘 측면으로만 생각했었음
프로그래머스 Level 2는 최대한 수학적으로 접근해야함.

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, vector<string>> clothesSet;
    
    for(vector<string> temp :  clothes){        
        vector<string> insert;
        if( clothesSet.end() != clothesSet.find(temp[1])){
            insert = clothesSet[temp[1]];
        }        
        insert.push_back(temp[0]);
        clothesSet[temp[1]] = insert;        
    }
    
    for(auto temp: clothesSet){
        answer *= (temp.second.size()+1);
    }
    answer -= 1; // 옷을 하나도 입지 않는 경우는 제외해야함.
    return answer;
}

 

시간초과 발생했던 DFS 알고리즘을 이용한 풀이는 아래와 같음.

 

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;


//답은 전부 맞지만 테스트 case 1 을 시간초과로 통과하지 못함...
int dfs(map<string, vector<string>> &clothesSet, int keyLocation, int &answer){   
    
    auto it = std::next(clothesSet.begin(), keyLocation);    
    
    for(int i=0; i < it->second.size(); i++){
        answer++;
        for(int k=keyLocation+1; k < clothesSet.size(); k++){            
            dfs(clothesSet, k, answer);        
        }        
    }    
    return 0;
}

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    map<string, vector<string>> clothesSet;
    
    for(vector<string> temp :  clothes){        
        vector<string> insert;
        if( clothesSet.end() != clothesSet.find(temp[1])){
            insert = clothesSet[temp[1]];
        }        
        insert.push_back(temp[0]);
        clothesSet[temp[1]] = insert;        
    }    
    for(int i=0; i < clothesSet.size(); i++){
        dfs(clothesSet, i, answer);
    }
    
    return answer;
}

 

꾸준히 하다보면 실력이 늘겠지..