[프로그래머스] 이모티콘 할인행사 with JS

알고리즘 스프린트 2일차 - [프로그래머스] Lv 2. 이모티콘 할인행사 (카카오 기출)

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

프로그래머스

 

소요시간

1시간 10분 (문제 잘못 이해하고 날린 시간 30분)

 

계획

- 할인율이 4가지 밖에 없다는 부분을 제대로 읽지 않아서 문제를 이상하게 이해했다

그리디 문제인 줄 알고 그리디로 구현하다가 뒤늦게 깨달았다...ㅠ

반복 부분을 제외하고 점수 합을 구하는 부분이랑 가입자 최대 값으로 초기화 하는 부분은 그대로 사용할 수 있을 것 같아서 그대로 사용하고, 반복을 돌렸던 부분을 중복순열 완전탐색으로 접근법을 바꿔서 풀었다.

 

풀이

• 중복 순열 완전탐색
  • 할인율은 중복이 가능하므로 중복 순열
  • 4가지의 할인율을 7가지의 이모티콘이 선택
  • 4의 7승 : 약 16000
  • 100명에 대해 16000개를 모두 확인하면
  • 워스트 케이스 : 약 160만
• 하나의 경우마다 사용자가 이모티콘 플러스를 구매하는지 확인하면
  
  • 워스트케이스 : 160만 * 7
• 천만번 반복 안으로 해결되니까 시간초과 우려는 없다
• 이모티콘 플러스를 구매한 유저의 수로 먼저 비교하고 같을 시에는 결제 금액으로 한번 더 비교한다

결과

코드

var salePer = []; 
var sale = [10, 20, 30, 40];
var len;
var answer = [0, 0];
function sum(target, emoticons, salePer){
    let sum = 0;
    for(let i = 0; i < emoticons.length; i++){
        if(salePer[i] >= target){
            sum += emoticons[i] - ((emoticons[i] * salePer[i]) / 100);
        }
    }
    return sum;
}

function solution(users, emoticons) {
    
    for (let i = 0; i < emoticons.length; i++){
        salePer.push(0);
    }
    len = emoticons.length;
    
    perm(0, users, emoticons);
    return answer;
}

function perm (idx, users, emoticons){
    if (idx == len){
        let temp_regist = 0;
        let temp_total = 0;
        for (let n = 0; n < users.length; n++){
            let tempSum = sum(users[n][0], emoticons, salePer);
            if (tempSum >= users[n][1]){
                temp_regist += 1;
            }
            else{
                temp_total += tempSum;
            }
        }
        if (temp_regist >= answer[0]){
            if(temp_regist > answer[0]){
                answer[0] = temp_regist;
                answer[1] = temp_total;            
            }
            else{
                if (temp_total > answer[1]){
                    answer[1] = temp_total;
                }
            }
        }
        return;
    }
    for(let i=0; i<4; i++) {
        salePer[idx] = sale[i]; 
        perm(idx+1, users, emoticons); 
    }
}

마치며

 오늘은 문제를 제대로 안 읽어서 시간을 낭비했다. 계획 자체는 1일차보다 꼼꼼히 작성했으나 문제를 제대로 읽지 않으면 무용지물이다라는 것을 느꼈고 다음번에는 문제를 더 잘 읽고 꼼꼼하게 계획해 보아야겠다.