[2021 Kakao blind recruitment] 메뉴 리뉴얼

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

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

DFS 로 풀 수 있다.. 초기에 바로 DFS를 떠올리지 못해서 삽질을 했다.

[풀이방법]

1. order 가 "abcfg" 라고 하고 course 가 2 일 경우, abcfg 에서 2개를 선택하는 조합을 구한다. (dfs)

ab, ac, af, ag ...

이거 하기전에 order 를 알파벳기준으로 정렬해주는 것도 필요하다.

2. 구한 경우들을 map 에 업데이트를 해준다.

map 에 존재하는 key일 경우 value++ 해주고 

없다면 map에 {key : 1}로 insert 해준다.

3. map 에 있는 value 의 최대값을 구한다.

map 의 value 를 기준으로 내림차순으로 정렬해준다.

map을 벡터에 복사해서, sort() 함수로 정렬할 수 있다.

4. value 가 최대값인 원소들의 key 값을 answer에 넣어준다.

1~4.를 반복한다.

5. answer 를 알파벳 기준으로 정렬해준다.

 

[코드]

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

using namespace std;

map <string, int> m;
bool visit[30];

bool compare(pair <string, int> a, pair <string, int> b) {
    return a.second > b.second;
}

void dfs(string order, int size, string s, int idx) {
    if(s.size() == size) {
        if(m.find(s) != m.end()) {
            m[s]++;
        }
        else
            m.insert(pair<string, int> (s, 1));
        return;
    }
    
    for(int i=idx; i<order.size(); i++) {
        if(visit[i]) continue;
        visit[i] = true;
        dfs(order, size, s+order[i], i+1);
        visit[i] = false;
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(auto c : course) {
        m.clear();
        
        for(auto order: orders) {
            sort(order.begin(), order.end());
            
            if(c <= order.size()) {
                dfs(order, c, "", 0);
            }
        }
        vector <pair<string, int>> v (m.begin(), m.end());
        sort(v.begin(), v.end(), compare);
        
        if(!v.empty()) {
            int max = v[0].second;
            
            if(max >= 2) {
                for(int i=0; i<v.size(); i++) {
                    if(v[i].second == max)
                        answer.push_back(v[i].first);
                    else
                        break;
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}