[PRG] 150368 이모티콘 할인행사 JAVA

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

프로그래머스

 

메모리: 73.2 MB

실행시간: 0.73 ms

 

문제분석

1. 서비스 가입자 최대
2. 판매액 최대

할인율을 적절히 적용해 우선순위 안에서 최대의 이득을 내야 한다 !
따라서, 모든 경우를 다 확인해본다 (중복 순열)

Go Go !

 

걸린시간

40분 ⏱️

 

풀이방법

1. 이모티콘 할인율 조합 구하기
2. 구매 비용 계산하기
 2-1. 본인 할인율 이상인 이모티콘 구매 (할인율 적용)
 2-2. 그 합이 본인 기준 이상일 경우 서비스 가입 
3. 서비스 가입 카운트하기
4. 우선순위 큐에 [가입자, 구매 비용] 넣기

 

포인트

서비스 가입자를 최대한 늘리면서 판매액도 높은 상황 구하기 !

우선순위 큐 : 가입자 내림차순 -> 구매 비용 내림차순

 

코드

import java.util.*;

class Solution {
    public static int[] sales = {10, 20, 30, 40};   // 할인율
    public static int[] num;                        // 순열 저장
    public static PriorityQueue<int[]> pq;          // 우선순위 큐
    public int[] solution(int[][] users, int[] emoticons) {
        // 순열 저장할 배열
        num = new int[emoticons.length];
        // 우선순위 큐 정렬조건 설정
        pq = new PriorityQueue<>(new Comparator<int[]>() {
            // 가입자 내림차순 -> 구매 비용 내림차순
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0];
            }
        });
        // 할인율 중복순열
        perm(0, users, emoticons);
        // 우선순위 가장 높은 상태 return
        return pq.poll();
    }
    // 중복순열
    public void perm(int r, int[][] users, int[] emoticons) {
        // 재귀함수 종료조건
        if(r == num.length) {
            // 구매 비용 및 서비스 가입자 계산
            int service = 0;    // 서비스 가입자
            int money = 0;      // 판매 비용
            
            for(int i = 0; i < users.length; i ++) {
                // 해당 사용자 구매 비용 합
                int sum = 0;
                for(int e = 0; e < emoticons.length; e ++) {
                    // 할인율 기준 확인
                    if(num[e] >= users[i][0]) {
                        sum += emoticons[e] * (100 - num[e]) / 100; // 할인율 적용
                    }
                }
                // 구매 비용이 기준 이상일 경우
                if(sum >= users[i][1]) service ++;  // 서비스 가입
                else money += sum;                  // 기준을 넘지 않으면 구매
            }
            // 계산 결과 pq에 대입
            pq.offer(new int[] {service, money});
            return;
        }
        // 할인율 대입하기
        for(int i = 0; i < sales.length; i ++) {
            num[r] = sales[i];
            perm(r + 1, users, emoticons);
        }
    
    }
}