Link | 프로그래머스 150368번 문제 : 이모티콘 할인행사
할인율의 개수가 4개이고 이모티콘의 개수도 최대 7개로 굉장히 적은 수이다.
그렇기 때문에 brute force로 각 이모티콘의 할인율을 결정한다.
모든 이모티콘의 할인율이 결정되면 모든 user를 순환하며 구독 여부와 수익을 계산한다.
이때 구독자가 최대인 경우를 구하고 추가로 구독자가 같다면 더 높은 수익을 선택한다.
Field
private final int[] DISCOUNT_VALUES = new int[]{10, 20, 30, 40};
private final Stack<Integer> discounts = new Stack<>();
private int[][] users;
private int[] emoticons;
private int maxSubs = 0, maxProfit = 0;
각 이모티콘 별로 할인율을 결정하는 방법은 백트래킹을 사용하였다.
private void search() {
if (emoticons.length == discounts.size()) {
// User 순환 탐색
// 최대 구독, 최대 수익 비교 결정
} else for (int d = 0; d < 4; d++) {
discounts.push(DISCOUNT_VALUES[d]);
search();
discounts.pop();
}
}
백트래킹에서는 Stack을 활용하였으며 이모티콘의 수와 Stack의 수가 같으면 user를 탐색한다.
int subs = 0, profit = 0;
for (int[] user : users) {
int payment = 0;
for (int i = 0; i < emoticons.length; i++)
if (discounts.get(i) >= user[0])
payment += emoticons[i] * (100 - discounts.get(i)) / 100;
if (payment >= user[1]) subs++;
else profit += payment;
}
User 순환 탐색이 끝나면 할인율에 따른 구독과 수익을 비교하여 최댓값을 결정한다.
if (subs > maxSubs) {
maxSubs = subs;
maxProfit = profit;
} else if (subs == maxSubs && profit > maxProfit) maxProfit = profit;
import java.util.Stack;
public class Solution {
private final int[] DISCOUNT_VALUES = new int[]{10, 20, 30, 40};
private final Stack<Integer> discounts = new Stack<>();
private int[][] users;
private int[] emoticons;
private int maxSubs = 0, maxProfit = 0;
public int[] solution(int[][] users, int[] emoticons) {
this.users = users;
this.emoticons = emoticons;
search();
return new int[]{maxSubs, maxProfit};
}
private void search() {
if (emoticons.length == discounts.size()) {
int subs = 0, profit = 0;
for (int[] user : users) {
int payment = 0;
for (int i = 0; i < emoticons.length; i++)
if (discounts.get(i) >= user[0])
payment += emoticons[i] * (100 - discounts.get(i)) / 100;
if (payment >= user[1]) subs++;
else profit += payment;
}
if (subs > maxSubs) {
maxSubs = subs;
maxProfit = profit;
} else if (subs == maxSubs && profit > maxProfit) maxProfit = profit;
} else for (int d = 0; d < 4; d++) {
discounts.push(DISCOUNT_VALUES[d]);
search();
discounts.pop();
}
}
}