[알고리즘 TIL] 이모티콘 할인행사

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=java

프로그래머스

프로그래머스 LV2. 시뮬레이션

설명

완전 탐색으로 구한다면, 100(사용자 수)*4(할인율 경우의 수)^7(이모티콘 개수)의 시간복잡도가 예상된다. 이모티콘의 개수가 크지 않아서 완전 탐색으로 통과되는 문제였다.

 

하지만, 4^n의 경우의 수를 구현하는 것이 쉽지 않았던 문제이다.

구현

import java.util.Arrays;

class Solution {

    static int sign = 0; //최대 회원 수
    static int earn = 0; //최대 수익

    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        int N = emoticons.length;
        int[] discountEmoticons = new int[N]; // 이모티콘 별 할인율 저장
        Arrays.fill(discountEmoticons, 10); // 10%로 초기화

        int totalCases = (int) Math.pow(4, N); // 4^N 가지의 조합
        for (int i = 0; i < totalCases; i++) {
            //특정 이모티콘들 할인율로 사용자들의 수익과 플러스 가입 수 계산 
            calculate(discountEmoticons, users, emoticons);
            //이모티콘들 할인율 갱신
            nextDiscount(discountEmoticons); // 다음 할인율 조합 생성
        }

        answer[0] = sign;
        answer[1] = earn;
        return answer;
    }

    // 이모티콘 중 하나를 10% 인상시키는 함수
    // 맨 뒷 인덱스부터 10%->...->40%순으로 증가시키며 할인율 고정
    // 해당 인덱스의 할인율을 10퍼 올리거나, 이미 40퍼인 경우 10%로 초기화 후 앞 인덱스 갱신
    private void nextDiscount(int[] discountEmoticons) {
    	//어떤 이모티콘을 인상시킬지 탐색
        int index = discountEmoticons.length - 1;
        while (index >= 0) {
            //해당 인덱스의 할인율이 40퍼 미만인 경우, 10퍼 인상
            if (discountEmoticons[index] < 40) {
                discountEmoticons[index] += 10;//하나 증가했으면 종료
                break;
            } else {
                //해당 인덱스의 할인율이 40퍼인 경우, 10퍼로 초기화의 앞 인덱스 상승
                discountEmoticons[index] = 10;
                index--;
            }
        }
    }

    private void calculate(int[] discountEmoticons, int[][] users, int[] emoticons) {
        int count = 0; // 가입자 수
        int earn_t = 0; // 현재 할인 조합에서의 수익

        for (int[] user : users) {
            int discount = user[0]; // 최소 원하는 할인율
            int price = user[1]; // 구매 한도
            int sum = 0;

            for (int i = 0; i < discountEmoticons.length; i++) {
                if (discountEmoticons[i] >= discount) {
                    sum += (emoticons[i] / 100) * (100 - discountEmoticons[i]); // 할인 적용된 가격
                }
            }

            if (sum >= price) count++; // 구매 한도 초과하면 플러스 가입
            else earn_t += sum; // 아니면 일반 구매 수익 증가
        }

        if (count > sign) {
            sign = count;
            earn = earn_t;
        } else if (count == sign) {
            if (earn < earn_t) earn = earn_t;
        }
    }​