[programmers] 이모티콘 할인행사

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

프로그래머스

 

emoticons 의 최대 크기는 7이고

할인율은 4가지(10%, 20%, 30%, 40%)이기 때문에 많지 않은 숫자임으로 중복 조합을 사용하였다.

 

/**
1. emoticons 중복조합
2. 중복 조합 경우로 최대 이모티콘 플러스 서비스 유저, 액수 구하기
**/
import java.util.*;

class Solution {
    static int minPercent;
    static int[] current;
    static List<int[]> statusList;
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        minPercent = 40;
        List<User> userList = new ArrayList<>();
        int count = emoticons.length;
        current = new int[count];
        statusList = new ArrayList<>();
        int max = 0;
        
        for(int[] user: users) {
            int percent = user[0];
            int limit = user[1];
            
            userList.add(new User(percent, limit));
        
            minPercent = Math.min(minPercent, percent);
        }
        // 5더하고 10으로 나누고 다시 더하면 1의 자리 반올림
        minPercent = (minPercent + 5)/10 * 10;
        
        duplicateCombination(0, count);
        
        for(int[] status: statusList) {
            for(int i = 0; i < count; i++) {
                for(User user: userList) {
                    if (user.percent <= status[i]) {
                        
                    }
                }
            }
        }
        
        List<Service> serviceList = new ArrayList<>();
        for(int[] status: statusList) {
            Service temp = new Service();
            for(User user: userList) {
                int total = 0;
                boolean sign = false;
                for(int i = 0; i < count; i++) {
                    if (status[i] >= user.percent) {
                        total += (100 - status[i]) * emoticons[i] / 100;
                        if (total >= user.limit) {
                            sign = true;
                            total = 0;
                            break;
                        }
                    }
                }
                if (sign) {
                    temp.user += 1;
                }
                temp.total += total;
            }
            
            if (max < temp.user) {
                max = temp.user;
            }
            serviceList.add(temp);
        }
        
        for(int i = serviceList.size() - 1; i >= 0; i--) {
            if(serviceList.get(i).user < max) {
                serviceList.remove(i);
            }
        }
        Collections.sort(serviceList);
        Service answerService = serviceList.get(0);
        
        answer[0] = answerService.user;
        answer[1] = answerService.total;
        
        
        return answer;
    }
    
    public void duplicateCombination(int index, int count) {
        if (index == count) {
            statusList.add(current.clone());
            return;
        }
        
        for(int i = minPercent; i <= 40; i+=10) {
            current[index] = i;
            duplicateCombination(index + 1, count);
        }
    }
}

class Service implements Comparable<Service>{
    public int user;
    public int total;
    
    public Service() {
        this.user = 0;
        this.total = 0;
    }
    
    public String toString() {
        return "{user: " + user + ", total: " + total + "}";
    }
    
    @Override
    public int compareTo(Service s) {
        if (this.user < s.user) {
            if (this.total < s.total) {
                return 1;
            } else if (this.total == s.total) {
                return 0;
            } else {
                return -1;
            }
        } else if (this.user == s.user) {
            if (this.total < s.total) {
                return 1;
            } else if (this.total == s.total) {
                return 0;
            } else {
                return -1;
            }
        } else {
            if (this.total < s.total) {
                return 1;
            } else if (this.total == s.total) {
                return 0;
            } else {
                return -1;
            }
        }
    }
}

class User {
    public int percent;
    public int limit;
    public int money;
    
    public User(int percent, int limit) {
        this.percent = percent;
        this.limit = limit;
        this.money = 0;
    }
    
    public String toString() {
        return this.percent + ", " + this.limit;
    }
}