[2023 KAKAO BLIND RECRUITMENT] 이모티콘 할인행사

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

프로그래머스

 

자잘한 조건이 많으므로 이를 놓치지 않고 잘 풀어야 한다.

• 우선 dfs를 사용하여 이모티콘들의 할인 조합을 만든다. 
• 그리고 각 조합마다 탐색하며, 플러스 가입 수와 이모티콘 판매액을 구한다.
• 그리고 플러스 가입자를 최대한 늘리는 것이 우선할 목표이고, 그 다음 목표가 이모티콘 판매액을 늘리는 것이므로 이 목표에 맞게 answer 값을 갱신한다.

참고로 dfs를 할 때 배열을 사용할 경우, 하나의 배열은 dfs 메소드의 여러 곳에서 참조되고, 이로 인해 해당 배열의 값이 의도치 않게 여러 곳에서 변경될 수 있다. 따라서 다음과 같이 종료 시 배열 값을 특정 어딘가(리스트)에 저장할 때는 배열을 복사해서 저장해야 한다. 그래야 해당 값이 변경되지 않는다.

public void dfs(int depth, int[] arr) {
    if (depth == emoticons.length) {
        saleList.add(arr.clone());
        return;
    }
        
    for (int i = 1; i <= 4; i++) {
        arr[depth] = i * 10;
        dfs(depth + 1, arr);
    }
}

 

전체 코드는 다음과 같다.

import java.util.*;

class Solution {
    
    int[][] users;
    int[] emoticons;
    List<int[]> saleList = new ArrayList<>();
    
    public int[] solution(int[][] users, int[] emoticons) {
        this.users = users;
        this.emoticons = emoticons;
        
        // 할인 조합 만들기
        dfs(0, new int[emoticons.length]);
        
        // 각 조합마다 판단
        int[] answer = new int[2];
        
        for (int[] sale : saleList) {
            int totalJoinCnt = 0;
            int totalBuyCost = 0;
            
            for (int[] user : users) {
                // user[0] : 비율, user[1]: 가격
                int buyCost = 0;
                for (int i = 0; i < emoticons.length; i++) {
                    if (sale[i] >= user[0]) { // user[0] 이상의 할인을 하면 구매
                        buyCost += emoticons[i] * (100 - sale[i]) / 100;
                    }
                }
                
                if (buyCost >= user[1]) { // 총 구매 금액에 user[1] 이상이면 플러스 가입
                    totalJoinCnt++;
                } else {
                    totalBuyCost += buyCost;
                }
            }
            
            // 플러스 가입자 수가 가장 많고, 구매 금액이 가장 많은 것이 답
            if (totalJoinCnt > answer[0]) {
                answer[0] = totalJoinCnt;
                answer[1] = totalBuyCost;
            } else if (totalJoinCnt == answer[0])  {
                if (totalBuyCost > answer[1]) {
                    answer[1] = totalBuyCost;
                }
            }
        }
        return answer;
    }
    
    public void dfs(int depth, int[] arr) {
        if (depth == emoticons.length) {
            saleList.add(arr.clone());
            return;
        }
        
        for (int i = 1; i <= 4; i++) {
            arr[depth] = i * 10;
            dfs(depth + 1, arr);
        }
    }
}

 

구글링으로 다른 사람들 풀이를 보니, 다음과 같이 푸는 게 더 효율적인거 같다!

• dfs 메소드에서 할인 조합이 만들어졌으면 그 자리에서 바로 calculate 메소드를 통해 해당 조합에 대해 계산한다. 
• 이렇게 하면 할인 조합들을 저장할 리스트가 필요 없으며, 리스트에 저장하기 위해 배열을 복사할 필요도 없다.

import java.util.*;

class Solution {
    
    int[][] users;
    int[] emoticons;
    int[] answer = new int[2];
    
    public int[] solution(int[][] users, int[] emoticons) {
        this.users = users;
        this.emoticons = emoticons;
        
        // 할인 조합 만들기 + 각 조합마다 판단
        dfs(0, new int[emoticons.length]);
        
        return answer;
    }
    
    public void dfs(int depth, int[] arr) {
        if (depth == emoticons.length) {
            calculate(arr);
            return;
        }
        
        for (int i = 1; i <= 4; i++) {
            arr[depth] = i * 10;
            dfs(depth + 1, arr);
        }
    }
    
    public void calculate(int[] sale) {
        int totalJoinCnt = 0;
        int totalBuyCost = 0;
        
        for (int[] user : users) {
            // user[0] : 비율, user[1]: 가격
            int buyCost = 0;
            for (int i = 0; i < emoticons.length; i++) {
                if (sale[i] >= user[0]) { // user[0] 이상의 할인을 하면 구매
                    buyCost += emoticons[i] * (100 - sale[i]) / 100;
                }
            }
            
            if (buyCost >= user[1]) { // 총 구매 금액에 user[1] 이상이면 플러스 가입
                totalJoinCnt++;
            } else {
                totalBuyCost += buyCost;
            }
        }
            
        // 플러스 가입자 수가 가장 많고, 구매 금액이 가장 많은 것이 답
        if (totalJoinCnt > answer[0]) {
            answer[0] = totalJoinCnt;
            answer[1] = totalBuyCost;
        } else if (totalJoinCnt == answer[0])  {
            if (totalBuyCost > answer[1]) {
            answer[1] = totalBuyCost;
            }
        }
    }
}