풀이 소요시간 : 40분
실수 없이 단번에 구현에 성공했다. 이런 비문학 지문같은 구현문제는 문제 읽으면서 멘탈 잘 관리하고, 정밀하게 코드 짜기만하면 풀 수 있는 경우가 잦은듯하다. 카카오 기출은 처음 풀어봤다.
구현 문제에 별다른 알고리즘을 넣는 경우는 없는 듯 하다. 해봤자 탐색
, 백 트래킹
정도를 요구한다.
전역변수화를 진행하면서 가격 조합 생성 방식을 고민했다. 백 트래킹 방식이 유일하다고 생각하여 Dfs()
으로 구현했다.
가격 조합 하나를 완성할 때 마다 Make_Result()
함수를 작동시켜 결과 가입자
, 매출액
값을 저장시켰다.
마지막으로 순차 정렬시킨 마지막 값을 정답으로 제출했다.
참고로 나는 구조체 사용을 아주 좋아한다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct User {
int Sale;
int Max;
};
struct Emo {
int Price;
};
vector<User> User_Vector;
vector<Emo> Emo_Vector;
int S[4] = {10, 20, 30, 40};
vector<int> Sale_Vector;
vector<pair<int ,int>> Result_Vector;
//가입자 수, 가격
void Make_Result() {
int Total_Sum = 0;
int Sign = 0;
//모든 회원 대상 검사
for(int i = 0; i < User_Vector.size(); i++) {
int Sale = User_Vector[i].Sale;
int Max = User_Vector[i].Max;
int Sum = 0;
//회원의 기준치에 부합한 이모티콘 가격의 합산이 이루어진다.
for(int j = 0; j < Sale_Vector.size(); j++) {
if(Sale_Vector[j] < Sale) continue;
int New_Price = ( Emo_Vector[j].Price * (100 - Sale_Vector[j]) ) / 100;
Sum += New_Price;
}
//합산 완료
if(Sum >= Max) {
//이모티콘 가입
Sign++;
}
else {
//이모티콘 구매
Total_Sum += Sum;
}
}
Result_Vector.push_back({Sign, Total_Sum});
//최종 가입자 수, 매출액 결과 저장
}
void Dfs(int Count) {
//모든 이모티콘의 할인율이 결정되면
if(Count == Emo_Vector.size()) {
Make_Result();
return;
}
//백 트래킹 -> [10, 10, 10, 10] ~ [40, 40, 40, 40] 의 모든 조합 생성
for(int i = 0; i < 4; i++) {
Sale_Vector.push_back(S[i]);
Dfs(Count + 1);
Sale_Vector.pop_back();
}
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
for(int i = 0; i < users.size(); i++) {
int Sale = users[i][0];
int Max = users[i][1];
User_Vector.push_back({Sale, Max});
}
for(int i = 0; i < emoticons.size(); i++) {
int Price = emoticons[i];
Emo_Vector.push_back({Price});
}
// 전역변수 세팅
Dfs(0);
// 조합 생성하기
sort(Result_Vector.begin(), Result_Vector.end());
int Ans_Sign = Result_Vector[Result_Vector.size() - 1].first;
int Ans_Total = Result_Vector[Result_Vector.size() - 1].second;
return {Ans_Sign, Ans_Total};
}