[Programmers] 2021 KAKAO BLIND RECRUITMENT : 메뉴 리뉴얼 (C++) with 조합!

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

프로그래머스

걸린 시간 : 31분 37초

---

여기저기서 끝도 없이 나오는 조합 문제이다. 조합을 정석적으로 알고 있기만 하면 어려울 게 없다.

조합

아래 코드가 내가 사용하는 조합이다. 코딩테스트 단골 주제니까 암기해두자.

또한, 여기서는 조합의 결과를 전역으로 선언한 것이지만 직접 조합의 결과를 파라미터로 넘겨주는 경우도 있다. 이러면 너무 컨테이너 자체를 들고다니는 것 같아서 난 위 코드처럼 짠다... 취향껏 짜자!

vector<T> ans;

void comb (vector<T>& src, int idx, int remain) {
	if (remain == 0) {
    	//조합이 끝난 것. 조합이 끝나면 해야할 코드 실행
        return;
    }
    if (idx == src.size())
    	return;
        
    //선택하는 경우
    ans.push_back(src[idx]);
    comb(src, idx+1, remain-1);
    ans.pop_back();
    
    //선택하지 않는 경우
    comb(src, idx+1, remain);
}

• 선택하는 것의 자료형을 T라고 두었다. 만약 이게 문자열이라면 ans와 src는 string이 될 것이다.
• comb() 함수의 파라미터는 3개이다. 뽑아낼 것이 있는 배열 src, 거기서 몇 번째 원소를 고를 차례인건지 idx, 뽑아야 할 남은 개수 remain.
• remain이 0이라면 조합이 끝난 후 해야할 것을 실행하고, idx가 src 크기를 넘어간다면 바로 끝낸다.
• 선택하는 경우는 ans에 해당 원소를 삽입한 후 조합을 이어서 실행하고, 실행 후에 그 원소를 바로 빼낸다.
• 선택하지 않는 경우는 그냥 idx만 1 더해서 이어서 실행하면 된다.

어렵지 않다!!

 

이 문제에서는 course의 원소 개수만큼 조합을 하고, 각각에서 최댓값을 찾아 구한 뒤 최댓값만큼 주문된 조합을 answer 벡터에 넣어주면 끝이다.

정답코드

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

using namespace std;

map<string, int> ordered;
string menu;

void comb (string& order, int idx, int remain) {
    if (remain == 0) {
        ordered[menu]++;
        return;
    }
    if (idx == order.size()) return;
    menu.push_back(order[idx]);
    comb(order, idx+1, remain-1);
    menu.pop_back();
    comb(order, idx+1, remain);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for (int num : course) {
        for (auto order : orders) {
            sort(order.begin(), order.end());
            comb(order, 0, num);
        }
        int mx = 0;
        for (auto e : ordered) {
            mx = max(mx, e.second);
        }
        if (mx > 1) {
            for (auto e : ordered) {
                if (mx == e.second) {
                    answer.push_back(e.first);
                }
            }
        }
        ordered.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}