프로그래머스 - 이모티콘 할인행사
2023 KAKAO BLIND RECUITMENT 이모티콘 할인행사 문제를 풀어보았다.
https://school.programmers.co.kr/learn/courses/30/lessons/150368
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
1. 이모티콘 플러스 서비스 가입자를 최대한 늘린다
-> 이모티콘 판매액이 사용자의 기준보다 높으면 이모티콘 플러스 서비스를 가입
-> 이모티콘을 최대한 사게 해서 판매액이 기준보다 높으면 가입을 많이 시킬 것
-> 주어진 사용자의 구매 이모티콘 할인 기준을 충족하는 이모티콘이 많을수록 좋을 것
2. 이모티콘 판매액을 최대한 늘리는 것
-> 이모티콘 플러스 서비스에 가입시키지 못한다면 최소 할인율로 구매하도록만 하면 될 것
제한 사항
이모티콘 할인율 10, 20, 30, 40, 할인율이 들어가는 emoticon의 개수는 7개까지, user는 100명까지
따라서 이모티콘 할인율의 경우의 수는 4^7개로 완전탐색을 통해 구현할 수 있을 것 같다.
이모티콘 플러스 서비스 가입자 수가 가장많은 경우 가입 수와 이모티콘 구매액을 출력하며, 가입 수가 같을 경우 이모티콘 구매액이 최대인 경우를 구하면 된다. (정렬)
풀이
import java.util.*;
class Solution {
class Kakao{
int total, amount;
public Kakao(int total, int amount){
this.total=total; this.amount=amount;
}
}
public static ArrayList<Kakao> answer = new ArrayList<>();
public static int[] discount = {10, 20, 30, 40};
public int[] solution(int[][] users, int[] emoticons) {
int[] dis = new int[emoticons.length]; // 각 인덱스에 이모티콘 할인율이 들어감
dfs(users, emoticons, dis,0);
Collections.sort(answer, (a,b) -> a.total == b.total ? b.amount-a.amount : b.total-a.total);
Kakao k = answer.get(0);
return new int[]{k.total, k.amount};
}
public void dfs(int[][] users, int[] emoticons, int[] dis, int cnt){
if(cnt == emoticons.length){ // 계산
int amount = 0;
int join = 0;
for(int i=0; i<users.length; i++){
int sum = 0;
for(int j=0; j<emoticons.length; j++){
if(users[i][0] <= dis[j]) sum += (emoticons[j]/100)*(100-dis[j]);
}
if(sum >= users[i][1]) join +=1;
else amount += sum;
}
answer.add(new Kakao(join, amount));
}
else{
for(int i=0; i<discount.length; i++){
dis[cnt] = discount[i];
dfs(users,emoticons,dis,cnt+1);
}
}
}
}각 이모티콘에 할인율을 어떻게 반영해줘야할 지 고민이 되었다..
따라서 첫 이모티콘부터 dfs를 시작하면서 dis배열에 할인율을 넣어주도록 하였다.
else{
for(int i=0; i<discount.length; i++){
dis[cnt] = discount[i];
dfs(users,emoticons,dis,cnt+1);
}
}dfs를 시작하게되면 dis 배열엔 전부 0이 들어가 있으며 첫 번째 이모티콘부터 10 할인율을 적용하며 첫 번째 if문을 통과할 땐 모든 이모티콘의 할인율이 10일 것이다. 이렇게 되면 맨 마지막 이모티콘부터 10 ~40 할인율 적용, 맨 마지막에서 두 번째가 20일 때 맨 마지막 10~40 적용하는 방식으로 4^7번 작동하게 될 것이다.
이렇게 되면 메모리는 얼마나 잡아먹을까..
제출한 결과
100MB까지 잡아먹기도 한다...
경우의 수가 많지 않고 모든 경우를 다 따져보려면 어쩔수없는 것인가.. 더 좋은 방법이 없을까 고민이 되었다..
시험장에서는 쉽게 못풀었을 것 같다.
정렬 기준에 대한 Comparator, dfs 구현 시 할인율을 어떻게 해야 완전탐색할 수 있을지를 잘 생각해야 했던 문제이다.