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

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

프로그래머스

1시간동안의 고민 후 풀리지 않아서 다른 분 (https://trillium.tistory.com/163)의 코드를 분석하고 푼 것을 작성해본다.

오늘도 못함을 깨닫고 한단계 성장해보자

문제 설명

문제 풀이

! 처음 내가 생각했던 문제 풀이

보고 생각한 것은 완전탐색으로 풀면 되지 않을까 생각했다. 이유는

1. 시간 복잡도 O(n*4^m) (n : 카카오톡 사용자, m : 이모티콘의 갯수) 이라서 최대 O(1638400)의 시간 복잡도를 갖는 다고 생각했고 이는 10초, 2GB memmory 상에서 가뿐히 될것이라 생각했다.
2. 따라서 재귀를 이용해서 풀면 되지 않을까 생각했다.

BUT, 1시간의 고민 사유

1. rate 와 price를 같이 관리를 할 것인데 어떤식으로 나타내는게 좋을까? (ArrayList? 새로운 Class?)

난 여기서 자바를 완전 모르고 있다고 생각했고, 공부해야겠다고 느꼈다. 

 

Trillium 님의 글로 인한 해결 

...
static List<Emoticon> emoList = new ArrayList<>();

static class Emoticon {
        int rate; // 이모티콘 할인율.
        int price; // 할인율을 적용한 가격.
        
        Emoticon(int rate, int price){
            this.rate = rate;
            this.price = price;
        }
    }
}

→ Emoticon 이라는 class를 생성 후, emoList라는 List의 생성으로 한번에 관리하는 법. 한수 배웁니다 ...

 

Code

import java.util.*;

class Solution {
    static int[] discountRate = {10, 20, 30, 40};
    static int[] answer = new int[2];
    static List<Emoticon> emoList = new ArrayList<>();
    
    public int[] solution(int[][] users, int[] emoticons) {
        recurEmoticon(users, emoticons, 0);
        return answer;
    }
    
    static void recurEmoticon(int[][] users, int[] emoticons, int index){
        if(index == emoticons.length){
            int[] result = proceedUser(users);
            // 우선순위 1.
            if (answer[0] < result[0]){
                answer = result.clone();
            }
            // 우선순위 2.
            if (answer[0] == result[0] && answer[1] < result[1]){
                answer = result.clone();
            }
            return;
        }
        
        for (int i = 0; i < 4; i++){
            int rate = discountRate[i];
            int discountPrice = emoticons[index] * (100 - rate) / 100;
            
            // 다른 rate의 emoticon 가격을 사용하는 경우를 쓰기위함. add, remove
            emoList.add(new Emoticon(rate, discountPrice));
            recurEmoticon(users, emoticons, index + 1);
            emoList.remove(emoList.size() - 1);
        }
    }
    
    static int[] proceedUser(int[][] users){
        int plusMember = 0;
        int totalPrice = 0;
        
        for (int i = 0; i < users.length ; i++){
            int userWishRate = users[i][0];
            int userMaxPrice = users[i][1];
            
            int userPurchasePrice = 0;
            for (Emoticon emo : emoList){
                if(userWishRate <= emo.rate){
                    userPurchasePrice += emo.price;
                }
            }
            
            // 허용가격 이상 구매하는지 판단. 
            if (userPurchasePrice >= userMaxPrice){
                plusMember ++;
            } else {
                totalPrice += userPurchasePrice;
            }
            
        }
        
        return new int[]{plusMember, totalPrice};
    }
    
    static class Emoticon {
        int rate; // 이모티콘 할인율.
        int price; // 할인율을 적용한 가격.
        
        Emoticon(int rate, int price){
            this.rate = rate;
            this.price = price;
        }
    }
}

---

고찰

카카오 코딩테스트를 연습하고, 공부하면서 내가 자바에 대해서 정확하게 알고 있지 않구나라고 생각한다. 더 배울게 많고 기억하고 있는게 많은데, 공부하지 않았던건가 생각했다. 객체지향 코드를 많이 좋아한다고 말한 내가 스스로 부끄러움을 얻을 정도로 이번 문제를 풀 때 아쉬움이 남는다..