문제 설명
카카오에서는 이모티콘 할인 행사를 하는데, 할인 행사의 목표는 총 두 가지가 있다. 첫째 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것, 둘째 이모티콘 판매액을 최대한 늘리는 것. 이때 무조건 첫 번째 목표를 우선시한다.
할인율은 10%, 20%, 30%, 40%가 주어진다. 사용자는 본인이 생각하는 할인율 이상이 되지 않으면 이모티콘을 사지 않는다. 만일 할인율이 이상이라면 무조건 해당 이모티콘을 산다. 또한 모든 이모티콘을 산 값이 본인의 가격 이상이라면 해당 이모티콘 구매를 취소한 뒤 플러스 서비스에 가입한다.
이때 플러스 서비스 가입자와 일반 이모티콘 구매가 최대가 되는 값을 구하라.
문제 풀이
처음 봤을 때는 꽤 막막했던 문제였다. 특히 문제 설명이 길어서 이걸 어떤 알고리즘을 써서 풀지? 싶었다. 그러나 찬찬히 문제를 살펴보니 제한사항에서 주어진 값들이 꽤 작고 또 효율성 테스트가 없는 것에 힌트를 얻었다. 바로 굳이 어떤 알고리즘을 쓰지 않고 그냥 해주면 된다는 것
첫 번째 접근
- 할인율의 가능한 모든 경우의 수 구하기
일단 할인율의 가능한 모든 경우를 구해줬다.
[10, 10, 10, 10], [10, 10, 10, 20], [10, 10, 10, 30]...
그리고 어느 한 경우의 수를 구하면 할인율을 구하도록 했다.
위의 경우의 수를 구하기 위해서 재귀 함수를 써줬다. 아마 이 문제에서 제일 머리를 많이 쓴 부분이 아닐까 싶다..
public static void bfs(int index, int[] emo, int[][] users){
if(index == emo.length){
/*
for(int a : arr){
System.out.print(a + " ");
}
System.out.println();*/
get_discount(emo, users);
return;
}
//rate로 가능한 모든 경우의 수
for(int i=0; i<4; i++){
arr[index] = rates[i];
index++;
bfs(index, emo, users);
index--;
}
}- 할인율을 적용한 값 구하기
유저 한 명당 만들어 놓은 할인율을 모두 적용해서 이모티콘의 총 합을 구했다. 이때 유저가 생각하는 할인율보다 해당 이모티콘의 할인율이 더 클 때만 계산을 하도록 했다. 또한 할인할 가격을 구한 다음에 본래 이모티콘 값에서 빼줘야 할인 된 이모티콘 값이 나온다.
이렇게 가능한 이모티콘을 모두 구입한 다음에 만일 생각하는 합보다 총합이 더 크면 플러스에 가입하도록 했다. 만일 그렇지 않다면 임시 값이 all_sum에 값을 더해줬다.
그렇게 모든 유저들을 계산한 다음 만일 현재의 최대 plus와 구한 plus가 같다면 sum이 더 큰 값을 넣어준다. 그리고 plus가 최대 plus보다 크다면 sum이 크든지 말든지 간에 plus가 더 큰 값을 넣어준다. 이는 plus를 우선시해야 한다고 했기 때문이다.
재귀함수 뿐만 아니라 플러스와 합 갱신에서도 신경을 써줘야 한다. 나는 처음에 plus와 sum이 둘 다 클 때만 갱신하도록 했는데, 이렇게 되면 plus가 우선시되지 않기 때문에 답이 나오지 않는다.
public static void get_discount(int[] emo, int[][] user){
int all_sum = 0;
int plus = 0;
for(int i=0; i<user.length; i++){
//현재 유저의 할인 기준과 플러스 기준
int[] cUser = user[i];
int uRate = cUser[0];
int uPrice = cUser[1];
int sum = 0;
//한 유저당 사는 이모티콘의 총 값
for(int j=0; j<emo.length; j++){
//만일 해당 이모티콘의 할인율이 유저의 할인율 보다 크거나 같다면
if(arr[j] >= uRate){
//할인율을 적용한 값을 더해준다.
sum += (emo[j] - (emo[j] * (arr[j] * 0.01)));
}
}
if(uPrice <= sum){
plus++;
//System.out.println(plus);
}else{
all_sum += sum;
}
}
//만일 plus의 수가 같다면 sum이 큰 걸 넣어준다.
if(plus == max_plus){
if(all_sum >= max_sum){
max_sum = all_sum;
}
}else if(plus > max_plus){
//만일 plus가 더 크다면 무조건 plus가 더 큰 값을 넣어야 한다. -> 1번 조건이 무조건 우선시되기 때문
max_plus = plus;
max_sum = all_sum;
}
}코드
class Solution {
public static int[] rates = {10, 20, 30, 40};
public static int[] arr;
public static int max_sum, max_plus;
public int[] solution(int[][] users, int[] emoticons) {
int[] answer = new int[2];
arr = new int[emoticons.length];
max_plus = 0;
max_sum = 0;
//System.out.println(7000 - (7000 * (20 * 0.01)));
bfs(0, emoticons, users);
answer[0] = max_plus;
answer[1] = max_sum;
//System.out.println(max_plus + " " + max_sum);
return answer;
}
public static void bfs(int index, int[] emo, int[][] users){
if(index == emo.length){
/*
for(int a : arr){
System.out.print(a + " ");
}
System.out.println();*/
get_discount(emo, users);
return;
}
//rate로 가능한 모든 경우의 수
for(int i=0; i<4; i++){
arr[index] = rates[i];
index++;
bfs(index, emo, users);
index--;
}
}
public static void get_discount(int[] emo, int[][] user){
int all_sum = 0;
int plus = 0;
for(int i=0; i<user.length; i++){
//현재 유저의 할인 기준과 플러스 기준
int[] cUser = user[i];
int uRate = cUser[0];
int uPrice = cUser[1];
int sum = 0;
//한 유저당 사는 이모티콘의 총 값
for(int j=0; j<emo.length; j++){
//만일 해당 이모티콘의 할인율이 유저의 할인율 보다 크거나 같다면
if(arr[j] >= uRate){
//할인율을 적용한 값을 더해준다.
sum += (emo[j] - (emo[j] * (arr[j] * 0.01)));
}
}
if(uPrice <= sum){
plus++;
//System.out.println(plus);
}else{
all_sum += sum;
}
}
//만일 plus의 수가 같다면 sum이 큰 걸 넣어준다.
if(plus == max_plus){
if(all_sum >= max_sum){
max_sum = all_sum;
}
}else if(plus > max_plus){
//만일 plus가 더 크다면 무조건 plus가 더 큰 값을 넣어야 한다. -> 1번 조건이 무조건 우선시되기 때문
max_plus = plus;
max_sum = all_sum;
}
}
}여담
기본적으로 알고리즘 문제는 1초에 1억번 계산을 한다고 생각한다.
이 문제에서는 이모티콘이 최대 7개이고 할인 비율의 수가 총 4개이니
4를 7번 곱해서 약 1,600번을 좀 넘는다.
그렇게 되면 유저가 최대 100, 이모티콘이 최대 7, 가능한 경우의 수가 1,6000이니
100 x 7 x 16000으로 약 1100만번의 연산을 거친다.
이는 꽤 많긴 해도 1억번보다 작은 숫자이니 효율성 테스트가 없으면 통과할만 하다.
