[ 프로그래머스 ] 150368 이모티콘 할인행사

codesver·2023년 3월 7일
0

Programmers

목록 보기
28/30
post-thumbnail

Link | 프로그래머스 150368번 문제 : 이모티콘 할인행사

📌 About

할인율의 개수가 4개이고 이모티콘의 개수도 최대 7개로 굉장히 적은 수이다.

그렇기 때문에 brute force로 각 이모티콘의 할인율을 결정한다.

모든 이모티콘의 할인율이 결정되면 모든 user를 순환하며 구독 여부와 수익을 계산한다.

이때 구독자가 최대인 경우를 구하고 추가로 구독자가 같다면 더 높은 수익을 선택한다.

📌 Solution

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;

📌 Code

GitHub Repository

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();
        }
    }
}
profile
Hello, Devs!

0개의 댓글