[프로그래머스] 메뉴 리뉴얼

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

코딩테스트 연습 - 메뉴 리뉴얼

 

-  구현, 백트래킹, hash 문제이다. 백트래킹을 사용할 때, 주어진 문제의 조건을 반드시 확인해야 한다. 문자열의 길이가 최대 10이므로, 조합에 대한 경우의 수는 10Cr * 20( 2 <= r <= 10) 이기 때문에, 백트래킹을 사용할 수 있다.

 

- 전체적인 풀이방식은,

 

1. 먼저, course에 적힌 숫자들이 r이 된다. 그래서 모든 order에 대해서 각각 나올수 있는 r개의 조합을 구한다.

 

2. course가 2인 경우, 각각의 order에서 나오는 r개의 조합을 찾는다. 이 때, 중복을 허용하지 않도록 dfs을 구현해야 

한다. 이 과정에서, 필자는 unordered_map을 통해 해당 조합이 몇 번 등장 했는 지를 hash로 구현했다. 또, 처음 hash에 들어갈 때 all_string 벡터에 해당 조합을 push했다.

 

3. 모든 order에 대해서 모든 2개의 조합을 다 찾았다면, all_string에 넣어두었던 이 조합들을 활용해서, 가장 많이 

등장한 조합을 찾았다. 특정 조합의 해쉬 값이 현재 까지의max보다 더 큰 경우, 새로 max를 갱신하고, temp_v 벡터를 clear 하고 해당 조합을 새로 temp_v에 넣어주었다. 만약 max값과 동일한 경우, 정답 조합을 담을 temp_v 벡터에 넣어주었다. 

 

4. 마지막으로 temp_v벡터의 모든 조합들을 answer벡터에 넣어준다. 

 

5. 이 과정을 모든 course에 대해 진행하고, 마지막으로 한 번 더 sort를 해 주면 끝

 

- 처음에 3번 테케를 통과하지 못해서 어떤 문제가 있을 지를 찾아보다가, 글자를 sorting 하지 않았다는 것을 깨달았다. 즉, 문제에서 WX와 XW를 동일한 조합으로 보았기 때문에, 처음에 특정 order에 대해 dfs를 시작할 때 해당 문자들을 모두 오름차순으로 재정렬 해 주어야 하는 것이었다. 

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

vector<string> all_string;
unordered_map <string,int> um;

void dfs(int count, int target,int index, string s, string order){
    if(count == target){
        if(um.find(s) != um.end()) {
            um[s]++;
        } else{
            um.insert({s,1}); 
            all_string.push_back(s);
        }
        return;
    }
    for(int i = index; i < order.length();i++){
        dfs(count+1, target, i+1, s+order[i], order);
    }
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i = 0; i < course.size(); i++){
        for(int j = 0; j < orders.size(); j++){
            vector<char> temp_v;
            for(int k = 0; k < orders[j].length();k++) temp_v.push_back(orders[j][k]);
            sort(temp_v.begin(), temp_v.end());
            string sorted_s;
            for(int k = 0; k < orders[j].length();k++) sorted_s+=temp_v[k];
            dfs(0,course[i], 0,"", sorted_s);
        }
        int max_num = 0; vector<string> temp_answers;
        for(int j = 0; j < all_string.size(); j++){
            if(um[all_string[j]] > 1 && um[all_string[j]] > max_num){ // max값 갱신
                max_num = um[all_string[j]];
                temp_answers.clear();
                temp_answers.push_back(all_string[j]);
            }
            else if (um[all_string[j]] == max_num && um[all_string[j]] > 1) {
                temp_answers.push_back(all_string[j]);
            } 
        }
        for(int j = 0; j < temp_answers.size(); j++) answer.push_back(temp_answers[j]);
        all_string.clear(); um.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}