이모티콘 할인행사

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

프로그래머스

 

 

문제 설명

 

주어진 정보와 조건을 활용해서 최대의 이모티콘 플러스 가입자 수와 판매액을 구하는 문제입니다.

 

조건1: 사용자들은 자신의 비율 이상 할인하는 이모티콘을 구매한다. (판매액 증가)

조건2: 사용자들의 구매 비용이 자신의 가격 이상이라면 이모티콘 플러스에 가입한다. (이모티콘 플러스 가입자 증가)

 

 

아이디어

 

어떤 문제든 가장 먼저 완전 탐색을 고려해야 합니다. (개인적인 원칙)

모든 이모티콘의 할인율을 하나하나 설정하고 모든 경우의 수를 구한다고 가정해봅시다.

1) 이모티콘의 최대 개수는 7이므로 이모티콘의 할인율을 결정하는 최대 경우의 수는 4^7입니다.

2) 또한, 유저는 최대 100명까지 있으므로 모든 경우의 수를 따지게 되었을 때의 시간복잡도는 4^7*100 = 약 160만 이 됩니다.

즉, 이 문제는 완전 탐색을 했을 때 1초 내로 충분히 풀 수 있는 문제입니다.

 

완전 탐색 아이디어를 돕기 위해 그림으로 표현해봤습니다.

 

1) 할인율 최대 경우의 수

 

각 할인율은 10~40까지 가능하고, 7자리가 있으므로, 경우의 수는 4^7 = 약 16000이 됩니다.

 

2) 전체 경우의 수

할인 정보 하나가 고정되어있을 때, 이모티콘 플러스 가입자수와 판매액을 구하기 위해서는 모든 유저를 탐색해야 합니다. => 최대 100

따라서, 전체 경우의 수는 100 * 4^7이며 약 160만이 됩니다.

즉, 시간복잡도는 O(160만) 입니다.

 

 

코드

 

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

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<vector<int>> results; // {이모티콘 플러스 서비스 가입자수, 이모티콘 판매액}
    int n = users.size();
    int m = emoticons.size();
    
    // 완탐 해도 되겠다 싶음. 시간복잡도 100*2^14 = 160만
    // 어떻게 완탐을 할 것인가? -> 4진수 표현 or 7중첩 for문
    int numMax = pow(4, m);
    for (int num = 0; num < numMax; num++) { // 할인 경우의 수 생성
        int brute = num;
        vector<int> discount; // 세일 정보(0: 10%, ... , 3: 40%)
        for (int div = 0; div < m; div++) {
            discount.push_back((brute % 4) * 10 + 10);
            brute = brute / 4;
        }
        
        int emoPlus = 0;
        int emoSales = 0;
        
        for (int userIndex = 0; userIndex < n; userIndex++) {
            int userDiscount = users[userIndex][0];
            int userMaxPrice = users[userIndex][1];
            int saleSum = 0;
            
            for (int discountIndex = 0; discountIndex < m; discountIndex++) {
                if (discount[discountIndex] >= userDiscount) {
                    // 구매
                    saleSum += emoticons[discountIndex] * (100 - discount[discountIndex] )* 0.01;
                }
            }
            
            if (userMaxPrice <= saleSum) {
                emoPlus++;
            } else {
                emoSales += saleSum;
            }
        }
        
        results.push_back({emoPlus, emoSales});
    }
    
    sort(results.begin(), results.end(), compare);
    return results[0];
}

 

이 코드는 제가 처음 풀었을 때 작성한 코드입니다.

처음 풀었을 때 작성한 주석을 제외하고 추가로 설명이 필요한 부분만 설명드리겠습니다.

 

1) 할인율 정보를 완전 탐색하는 방법

저는 2가지를 고려했습니다. 그 중 첫 번째 방식은 7중 for문을 사용하는 것입니다. 정말 확실하고 실수 없는 방법이지만, 그만큼 꼴뵈기 싫은 코드이기도 합니다. 

두 번째 방식은 4진수를 활용하는 방식입니다. 0000, 0001, 0002, 0003, 0010, ... 3333 이런 방식으로 4진수를 통해 수를 나타내고 0: 10% 할인, 3: 40% 할인 으로 설정하면 모든 할인 경우의 수를 탐색할 수 있습니다.

discount.push_back((brute % 4) * 10 + 10);

 

이렇게 작성한 이유는, 4진수의 수가 0이 되었을 때 10으로 리턴을 하고, 1 -> 20, 2 -> 30, 3 -> 40 을 리턴하기 위해서입니다.

 

 

할인율 정보를 완전 탐색하는 또다른 방법

 

DFS로도 16000가지의 탐색을 진행할 수 있습니다.

 

의사 코드(?)만 추가하겠습니다.

이런 식으로도 모든 탐색을 할 수 있습니다.

이런 방식은 배울만 한 것 같습니다. 제가 사용한 n진수 방식은 바로 안떠오를 때도 있고, 실수할 여지도 있기 때문입니다.

다만, dfs로 너무 깊게 함수를 들어가면 overflow가 발생할 수 있으니, 이 부분만 조심하면 좋을 것 같습니다.

 

 

혹시 제가 놓친 부분이나 실수한 부분이 있다면 알려주시면 감사하겠습니다.