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;
}
'Programmers' 카테고리의 다른 글
[Programmers] 정수 삼각형 (C++) (0) | 2023.10.12 |
---|---|
[Programmers] JadenCase (C++) (0) | 2023.10.12 |
[Programmers] 최댓값과 최솟값 (C++) with 문자열 파싱 (토큰 분리) (0) | 2023.10.08 |
[Programmers] 2021 KAKAO BLIND RECRUITMENT : 합승 택시 요금 (C++) with 플로이드 (1) | 2023.10.04 |
[Programmers] 2020 KAKAO BLIND RECRUITMENT : 문자열 압축 (C++) (0) | 2023.09.17 |