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

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

프로그래머스

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 이모티콘 할인행사 

 

문제 접근

백트래킹 문제이다! 

 

핵심 정리  

- 문제에서 원하는 가장 큰 우선순위는 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것 

- 이모티콘 판매액을 최대한 늘리는 것 

 

이모티콘 플러스 서비스 가입자의 이모티콘 판매액은 count하지 않는다. 

즉 이모티콘 판매액은 서비스 가입자가 아닌 사람의 이모티콘 구매이다. 

 

할인율은 항상 10,20,30,40 중 하나로 설정이다. 

 

이모티콘 플러스 서비스 가입자의 가입 기준은 

사용자의 총 구매 비용의 합이 해당 사용자 기준의 일정 가격 이상이면 서비스 가입을 한다. 

 

이모티콘 구매 기준은 해당 사용자의 일정 비율 이상 할인하는 이모티콘을 구매한다. 

 

1. static 변수로 바꾸기 

static int n;           // 이모티콘 개수 
static int [] memo;     // 백트래킹 기록용 
static int [][] user;   // 유저 
static int [] emoticon; // 이모티콘 
static int answer1 = 0; // 최대 가입자 
static int answer2 = 0; // 최대 판매액 

public int[] solution(int[][] users, int[] emoticons) {
    n = emoticons.length;
    memo = new int [n];
    user = new int [users.length][2];
    for(int i = 0; i < users.length; i++){
        user[i][0] = users[i][0];
        user[i][1] = users[i][1];
    }
    emoticon = Arrays.copyOf(emoticons, n);
    // ... 생략 
}

 

2. 백트래킹 하기 

 

각 이모티콘들의 할인율은 10~40퍼 고정이다. 

이모티콘의 개수는 최대 7개이다. 

그럼 백트래킹으로 나오는 경우의 수는 최대 4^7승이다. 

충분히 백트래킹으로 구할 수 있는 경우의 수 

 

해당 결과를 memo에 저장 

backtracking(0);

public static void backtracking(int depth){
    if(depth == n){
        calculate();
        return;
    }
    // 할인율 10 ~ 40퍼 
    for(int i = 10; i <= 40; i += 10){
        memo[depth] = i;
        backtracking(depth + 1);
    }
}

 

3. 본격적인 계산하기 

 

먼저 각 이모티콘의 할인된 가격을 계산한다. 

int [] price = new int [n]; // 각 이모티콘 할인된 가격 
for(int i = 0; i < n; i++){
    price[i] = emoticon[i] * (100 - memo[i]) / 100;
}

 

이번 백트래킹에서 서비스 가입자 숫자와 서비스 가입자가 아닌 사람들의 이모티콘 판매액 기록 변수 선언 

 int cnt1 = 0; // 이모티콘 플러스 서비스 가입자 숫자 
 int cnt2 = 0; // 이모티콘 플러스 가입자x 이모티콘 누적 금액

 

user 숫자만큼 for문 반복 

sum: 해당 사용자 이모티콘 구매 누적 금액 

flag: 이번 사용자가 이모티콘 플러스 가입 체크 용도 

만약 sum(구매 누적 금액)이 사용자 기준의 일정 가격 이상이 된다면 이모티콘 플러스 서비스 가입 flag = true

 

만약 flag = true 즉 서비스 가입을 했다면 cnt1(이모티콘 서비스 가입자 숫자)++

false 라면 cnt2(이모티콘 플러스 가입자x 이모티콘 누적 금액) += sum

for(int i = 0; i < user.length; i++){
    int sum = 0; // 사용자 이모티콘 구매 누적 금액
    boolean flag = false; // 이모티콘 플러스 가입 체크 
    for(int j = 0; j < n; j++){
        if(memo[j] >= user[i][0]){
            sum += price[j];
        }
        if(sum >= user[i][1]){
            flag = true;
            break;
        }
    }
    if(flag){
        cnt1++;     // 이모티콘 플러스 가입자 추가 
    }
    else{
        cnt2 += sum; // 이모티콘 판매액 
    }
}

 

3가지 case 

 

항상 우선순위(priority)는 이모티콘 서비스 가입자를 최대한 늘리는 것 

 

1) 현재 최대 서비스 가입자 숫자(answer1) 보다 서비스 가입자가 적으면 return 한다. 

 

2) 만약 이번 케이스가 answer1(서비스 가입자)보다 더 크면 모두 갱신한다.

answer1 = cnt1;

answer2 = cnt2;

 

3) 만약 이번 케이스가 answer1가 같은데 판매액은 더 많으면 answer2를 cnt2로 갱신한다. 

전체 코드

import java.util.*;
class Solution {
    static int n;           // 이모티콘 개수 
    static int [] memo;     // 백트래킹 기록용 
    static int [][] user;   // 유저 
    static int [] emoticon; // 이모티콘 
    static int answer1 = 0; // 최대 가입자 
    static int answer2 = 0; // 최대 판매액 
    public int[] solution(int[][] users, int[] emoticons) {
        n = emoticons.length;
        memo = new int [n];
        user = new int [users.length][2];
        for(int i = 0; i < users.length; i++){
            user[i][0] = users[i][0];
            user[i][1] = users[i][1];
        }
        emoticon = Arrays.copyOf(emoticons, n);
        
        backtracking(0);
        
        return new int[]{answer1, answer2};
    }
    public static void backtracking(int depth){
        if(depth == n){
            calculate();
            return;
        }
        // 할인율 10 ~ 40퍼 
        for(int i = 10; i <= 40; i += 10){
            memo[depth] = i;
            backtracking(depth + 1);
        }
    }
    public static void calculate(){
        int [] price = new int [n]; // 각 이모티콘 할인된 가격 
        for(int i = 0; i < n; i++){
            price[i] = emoticon[i] * (100 - memo[i]) / 100;
        }
            
        int cnt1 = 0; // 이모티콘 플러스 서비스 가입자 숫자 
        int cnt2 = 0; // 이모티콘 플러스 가입자x 이모티콘 누적 금액 
        
        for(int i = 0; i < user.length; i++){
            int sum = 0; // 사용자 이모티콘 구매 누적 금액
            boolean flag = false; // 이모티콘 플러스 가입 체크 
            for(int j = 0; j < n; j++){
                if(memo[j] >= user[i][0]){
                    sum += price[j];
                }
                if(sum >= user[i][1]){
                    flag = true;
                    break;
                }
            }
            if(flag){
                cnt1++;     // 이모티콘 플러스 가입자 추가 
            }
            else{
                cnt2 += sum; // 이모티콘 판매액 
            }
        }
        
        if(answer1 > cnt1) return; // 서비스 가입자가 적으면 return 
        
        if(answer1 < cnt1){  // 서비스 가입자가 더 크면 갱신
            answer1 = cnt1;
            answer2 = cnt2;
        }
        else if(answer2 < cnt2){ // 서비스 가입자는 같은데 판매액이 더 크면 갱신 
            answer2 = cnt2;
        }
    }    
}

 

댓글과 공감은 취준생에게 많은 힘이 됩니다 ㅎㅎ