이모티콘 할인행사

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

프로그래머스

입력 파라미터 값의 제한을 보고 시간 복잡도를 걱정할 문제라고 생각이 안들었다.

시간 복잡도가 필요하다면 좋은 아이디어로 접근해야 한다.

 

문제 풀이는 전체 경우의 수 ( 최대 4^7 ) 의 케이스에서 Best 를 찾아본다.

 

할인율은 10, 20, 30, 40 ( 총 4 개 ) 의 케이스이기에 n 개의 이모티콘의 경우의 수를 만들고 ( N )

유저의 수 ( N ) 에서 이모티콘의 구입과 서비스 가입 유무를 판단한다.

 

비용은 N^2 * 4 로 할인율이 정해지지 않았다면 어려웠을 풀이 접근이다.

function solution(users, emoticons) {
    var discountCase = [0.9, 0.8, 0.7, 0.6];
    var answer = [0, 0];

    var emoticon_count = emoticons.length;
    // 4 ^ n ( n <= 7 )
    var total_count = discountCase.length ** emoticon_count;

    // generate sample '[0, 0, 0, 0 ...]'
    for(var i = 0; i < total_count; i++) {
        var j = i;

        var sample = new Array(emoticon_count);
        var sample_idx = emoticon_count;
        // 10 digit -> 4 digit
        while (j > 0) {
            sample[--sample_idx] = j % 4;
            // division by '4'
            j = j >> 2;
        }
        while (sample_idx > 0) {
            sample[--sample_idx] = 0;
        }

        var sample_result = [0, 0];
        users.forEach(user => {
            var [discount, budget_service_cash] = user;

            var discount_margin = (discount / 10) - 1;
            var total_cash = 0;
            for (var i = 0; i < emoticon_count; i++) {
                if (sample[i] >= discount_margin) {
                    total_cash += emoticons[i] * discountCase[sample[i]];
                }
            }

            if (total_cash >= budget_service_cash) {
                sample_result[0] += 1;
            } else if (total_cash > 0) {
                sample_result[1] += total_cash;
            }
        });

        if((sample_result[0] > answer[0]) 
        || (sample_result[0] == answer[0] && sample_result[1] > answer[1])) {
            answer = sample_result;
        }
    }
    
    return answer;
}