[Java] 프로그래머스 이모티콘 할인

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=java# 

프로그래머스

풀이

최적화를 해서 풀까? 싶다가 나이브하게 brute force로 충분히 패스 가능한 시간복잡도를 가졌다. 

로직은 다음과 같다. 

1. dfs 재귀 탐색으로 완탐한다. 
2. 각 레벨마다 4가지 할인율의 정보를 disInfo 배열에 담는다. 
3. 리프 노드에서 조건에 따른 사용자의 경우의 수를 따져 list에 추가한다.
4. 모든 경우의 수 ( 가입자 수 , 판매액 ) 를 담은 배열을 가입자 수 기준 오름차순 정렬하고 리턴한다. 

나이브한 풀이가 가능한 이유는 재귀 레벨의 최대 길이  = 7, 각 재귀마다 하는 행동 4 

재귀마다 4번의 액션을 취함으로 4 ^ 7

리프 노드에서 for문 최대 개수 = 100 * 7 = 700

 

따라서 조합의 최대 수 = 700 * 4^7 < 1억 이다. (보통 연산횟수가 1억 넘어가면 tle라고 생각하면된다. ) 

따라서 브루트 포스로 구현하면 된다 .

 

코드

import java.util.*;

class Solution {
    int dis[] = {10,20,30,40};
    int userLen, emoLen;
    ArrayList<int[]> ans ;
    public int[] solution(int[][] users, int[] emoticons) {
        ans = new ArrayList<>();
        int[] answer ;
        userLen= users.length;
        emoLen = emoticons.length;
        ans.add(new int[]{0,0});
        

	//모든 경우의 수를 리스트에 담는다. 
        dfs(users,emoticons, new int[emoLen], 0 );
    //리스트 소팅
        Collections.sort(ans, (a,b)-> b[0]-a[0] == 0 ? b[1]-a[1] : b[0]-a[0]);
	//답을 리턴한다.
        return ans.get(0);
    }
    public void dfs(int[][] u, int[] e,int[] disInfo, int level){
        if(level == emoLen){//종료 조건
            int buyCnt = 0 ;
            int buySum = 0;
            
            for(int i = 0 ;i < userLen ;i++){
                int sum = 0 ;
                for(int j =0 ; j< emoLen; j++){
                    if(disInfo[j] >= u[i][0]) 
                        sum+= e[j]/100*(100-disInfo[j]);
                }
                if(sum >= u[i][1]){
                    buyCnt++;
                }else{
                    buySum += sum;
                }    
            }
            ans.add(new int[]{buyCnt,buySum});
            return;
        }else{
            for(int i = 0 ;i < 4 ;i++){
                disInfo[level] = dis[i];
                dfs(u,e,disInfo, level+1);
            }
        }
    }
}