문제링크

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

구현방법

효율성 체크는 안함.

10초 내에만 돌아가면된다.

유저 최대 길이 100

이모티콘 최대 길이 -> 7개

이모티콘의 원소는 100의 배수

할인율은 10 ,20 ,30 ,40 4가지존재 16000가지

-> 이 경우의 수를 전부 뽑아서 만들고 이 값을 통해서 계산 사용자 계산

-> answer 배열의 앞 -> 이모티콘 플러스 산 사람

-> answer 배열의 뒷 -> 이모티콘 구매 비용.

총 경우 100 7 16000 -> 약 1100만번의 수행 -> 탐색을 진행해도 무리가 없다.

목표

이모티콘 플러스 서비스 가입자를 최대한 늘리는 것

두번쨰로 판매액을 늘리는 것임.

그러니까

첫번째로 이모티콘 플러스 가입자가 가장 많은 경우 가 최우선 답

플러스 가입자가 같은 경우 -> 이모티콘 판매액이 최대인경우가 값임.

중복 조합 및 탐색을 통해서 할인율의 경우를 전부 구하고 그 값을 계산해서 문제가 제시한 기준에 맞춰서 최대값을 갱신해준다.

• 생각보다 문제를 이해하면 어렵지 않은 문제였다.

알고리즘

탐색 및 중복 조합

CODE

class Solution {

    int sale[] = {10,20,30,40};

    int size;

    int[] answer;

    int[] Combi;

    public int[] solution(int[][] users, int[] emoticons) {
        answer = new int[2];

        answer[1] = Integer.MIN_VALUE;

        size = emoticons.length;

        Combi = new int[emoticons.length];

        Start(users,emoticons,0);
        return answer;
    }

    private void Start(int[][] users, int[] emoticons,int depth) {
        if(depth == size){
            
            //계산 시작
            int result[] = calc(users,emoticons, Combi);

            //이모티콘 플러스 가입자가 더많은 게 먼저
            if(result[0] > answer[0]){
                answer[0] = result[0];
                answer[1] = result[1];
                //가입자가 같은 경우 -> 이모티콘 판매액이 더 큰것으로 변경
            }else if(answer[0] == result[0] && result[1] > answer[1]){
                answer[0] = result[0];
                answer[1] = result[1];
            }

            return;
        }
        
        for(int idx = 0;idx <sale.length;idx++){
            Combi[depth] = sale[idx];
            Start(users,emoticons,depth+1);
        }
        
    }

    //총 계산
    private int[] calc(int[][] users, int[] emoticons, int[] combi) {

        int check[] = new int[2];


        for(int user = 0; user < users.length;user++){
            int sum = 0;

            for(int len = 0; len <emoticons.length;len++){
                //할인율이 유저가 원하는 만큼 이상인경우만
                if(combi[len] >= users[user][0]) {
                    int Calc = emoticons[len] - ((emoticons[len]/100) * combi[len]);
                    sum += Calc;
                }
            }

            //유저가 원하는 값보다 이상인경우
            if(sum >= users[user][1]){
                check[0] +=1;
                //유저가 원하는 값보다 미만인경우
            }else{
                check[1] += sum;
            }
        }

        return check;
    }
}