프로그래머스 - 이모티콘 할인행사 (c++)

c4fiber·2023년 3월 19일
0

code-interview

목록 보기
5/12

요약 및 과정

  • 요약
    • 모든 경우의 수를 체크하는 문제(brute force)
  • 과정
    • 어떻게 최고효율이 나오는 값이 나올까 하다가 이모티콘 수의 제한을 보고 모두 테스트 해보기로 했다.
    • discount 함수를 미리 만들어둬서 활용할 생각 -> percentage에 따라 바로 계산이 가능하므로 폐기
    • 각 경우의 수를 정할 percentage를 어떻게 얻을 것인가 -> https://jja2han.tistory.com/261 의 글을 참고해서 재귀적으로 구현했다.
    • 위에서 언급한 방식을 활용하니 모든 반환값을 활용할 수 없어서 전역변수를 이용햇다.
    • max_element 함수를 활용해서 코드를 간결화 했다.

구현

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

using namespace std;

vector<vector<int>> profits; // 모든 경우의 수를 저장할 변수

// 할인율(percent) 정해지면 계산 후 결과를 profits에 저장하는 함수
void addProfit(vector<vector<int>> users, vector<int> emoticons, vector<int> percents) {
    int membership = 0;
    int money = 0;

    // 모든 유저에 대해서 주어진 percents를 활용해 이익 계산
    for(auto user : users) {
        int spendMoney = 0;

        for(int i=0; i<emoticons.size(); i++) {
            if (user[0] > percents[i] ) continue;

            spendMoney += emoticons[i] * (100 - percents[i]) / 100;
        }

        // 멤버십을 가입하는지 안하는지 판단
        if (spendMoney >= user[1]) {
            membership += 1;
        }else {
            money += spendMoney;
        }
    }

    profits.push_back({membership,money});
}

// 모든 percent의 경우의 수를 만들어 addProfit을 호출하는 함수 (재귀적으로 구현)
void setPercentAndCalc(vector<vector<int>> users, vector<int> emoticons, vector<int> percents) {
    if (emoticons.size() == percents.size()) {
        addProfit(users, emoticons, percents);

        return;
    }

    for(int i=10; i<=40; i+=10) {
        percents.push_back(i);
        setPercentAndCalc(users, emoticons, percents);
        percents.pop_back();
    }
}

// max_element에 활용할 compare 함수 ( 우선순위: membership, 이모티콘 구매금액)
bool compare(vector<int> a, vector<int> b) {
    if(a[0] == b[0]) {
        return a[1] < b[1];
    }

    return a[0] < b[0];
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer;
    vector<int> percents;

    setPercentAndCalc(users, emoticons, percents);

    answer = *max_element(profits.begin(), profits.end(), compare);


    return answer;
}

후기

직접 응시하면서 풀었던 문제중에 하나 였다.

당시에 재귀적 구현을 통해 모든 경우의 수를 만드는 것에 실패해서 풀지 못했던 문제다.

모든 경우의 percent를 구하는 방법을 다른문제풀이에 활용할 수 있을 것 같다.

profile
amazing idiot

0개의 댓글