[programmers] 150368번 - 이모티콘 할인행사 (brute force, 2023 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제

 

 완전탐색 조합문제이다. 카카오는 이제 구현이 베이스로 깔리는 것 같다. 문제를 나누는 카테고리는 따로 있어도 뭔가 복잡한 구현을 해야하는 느낌이다.

 

 이런 구현은 많은 문제를 풀어보는 방법밖에 없나 싶다.. 약 20분에서 30분 정도 걸렸다. 실제로는 정해진 5시간 안에 여러 문제를 풀어야한다는데... 집중력 떨어지는 입장으로서 걱정이 많이 된다.

---

 

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

프로그래머스

---

2. 풀이과정

 

 사실 풀이 과정은 단순하다. 그러나 앞에서 말했듯이 이런 문제들은 구현을 하는 과정에서 잔실수가 많아지기 때문에 정답률이 다소 낮은 것 같다.

 

 어떤 문제든 똑같겠지만 특히나 구현문제는 초반 설계를 매우 매우 매우 확실하게 하고 한 번의 제출로 문제를 끝내는 것이 제일 좋다고 생각한다.

 

 문제를 나누면 다음과 같다.

 

1. 이모티콘 할인율의 조합을 구한다.

- 해당 부분을 재귀함수로 해결하였다. 조합을 구하는 문제는 재귀함수가 최고인 것 같다... 가독성도 줄고 구현이 훨씬 편해진다.

2. 조합이 완성되면 각 user마다 이모티콘을 구매하는지, 혹은 plus 요금제에 가입하는지를 계산한다.

3. answer와 비교하며 정답을 구한다.

 

 다음은 정답코드이다.

 

#include <string>
#include <vector>

using namespace std;

int dis_rate[4] = { 10, 20, 30, 40 };
int emoticons_size;

int rates_index[7] = { 0 };
vector<vector<int>> global_users;
vector<int> global_emoticons;
vector<int> answer;

void comb_rate(int index) {
    if (index == emoticons_size) {

        int plus_user = 0;
        int count_cost = 0;

        for (int user = 0; user < global_users.size(); user++) {

            int count = 0.0;

            for (int emoticon = 0; emoticon < emoticons_size; emoticon++) {
                if (global_users[user][0] <= dis_rate[rates_index[emoticon]]) {
                    count += global_emoticons[emoticon]
                        * (100.0 - dis_rate[rates_index[emoticon]]) / 100;
                }
            }

            if (count >= global_users[user][1])
                plus_user++;
            else
                count_cost += count;
        }

        if (answer.size() == 0) {
            answer.push_back(plus_user);
            answer.push_back(count_cost);
        }
        else if (answer[0] < plus_user || (answer[0] == plus_user && answer[1] < count_cost)) {
                answer[0] = plus_user;
                answer[1] = count_cost;
        }
    }
    else {
        for (int i = 0; i < 4; i++) {
            rates_index[index] = i;
            comb_rate(index + 1);
        }
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {

    emoticons_size = emoticons.size();
    global_users = users;
    global_emoticons = emoticons;

    comb_rate(0);

    return answer;
}

 

 comb_rate() 재귀함수를 보면 마지막까지 조합이 구해지면 계산을 시작한다. 코드의 윗부분을 보면 알겠지만 변수를 좀 많이 사용하였는데, 구현이 더욱 편하게 느껴졌다.

 

 최대의 수로 들어와봤자 4 * n * n * m의 시간복잡도로 해결할 수 있었다.

 

3. 결어

 

 한 번의 제출로 정답이 나와서 뿌듯했다. 초반 설계에서 최대한의 오류를 잡는 법을 더 공부해야겠다.