코딩테스트/프로그래머스
[프로그래머스] 이모티콘 할인행사 풀이 및 코드 분석
by 현걸
2025. 3. 20.
문제 링크
1. 문제 분석
📌 문제 개요
- 각 이모티콘에 대해 할인율(10%, 20%, 30%, 40%)을 결정해야 함
- 모든 사용자가 특정 할인율 이상의 이모티콘을 구매하며, 특정 금액 이상 사용하면 이모티콘 플러스에 가입
- 목표:
- 이모티콘 플러스 가입자를 최대로 늘리기
- 이모티콘 판매 수익을 최대로 늘리기
2. 해결 방법
🔹 완전 탐색 (백트래킹)
- 이모티콘 개수
E
가 최대 7개로 적기 때문에, 4^E(= 4^7 = 16384) 경우의 수를 탐색해도 무리가 없음.
- 각 이모티콘이 가질 수 있는 할인율 (10%, 20%, 30%, 40%) 중 하나를 선택하는 모든 경우의 수를 확인
- 백트래킹을 사용하여 가지치기하면서 탐색 진행
3. 코드 구현 (Java)
class Solution {
static int U, E;
static int[] price, answer;
static int[] discount = {40, 30, 20, 10};
public int[] solution(int[][] users, int[] emoticons) {
answer = new int[2];
U = users.length;
E = emoticons.length;
price = new int[U];
comb(0, users, emoticons);
return answer;
}
public void comb(int d, int[][] users, int[] emoticons) {
if(d == E) {
int sum = 0, cnt = 0;
for(int i=0; i<U; i++) {
if (price[i] >= users[i][1]) cnt++;
else sum += price[i];
}
if(answer[0] < cnt) {
answer[0] = cnt;
answer[1] = sum;
} else if (answer[0] == cnt) {
answer[1] = Math.max(answer[1], sum);
}
return;
}
for(int i = 0; i < 4; i++) {
int p = emoticons[d] * (100 - discount[i]) / 100;
for(int u = 0; u < U; u++) {
if(users[u][0] <= discount[i])
price[u] += p;
}
comb(d+1, users, emoticons);
for(int u = 0; u < U; u++) {
if(users[u][0] <= discount[i])
price[u] -= p;
}
}
}
}
4. 코드 분석
🔹 주요 알고리즘
- 할인율을 4가지 중 하나로 선택 (완전 탐색)
- 각 이모티콘마다 4가지 할인율(10%, 20%, 30%, 40%) 중 하나를 선택
- 백트래킹 (재귀 호출)으로 모든 경우 탐색
- 사용자별 구매 비용 계산
- 사용자의 할인 기준 이상이면 구매
- 구매 비용이 특정 금액 이상이면 이모티콘 플러스 가입
- 가입자 수와 판매 수익 비교
- 가입자가 많은 경우 최우선
- 가입자가 같다면 판매 수익이 높은 경우 선택
5. 시간 복잡도 분석
E <= 7
- 가능한 할인율 경우의 수 =
4^E
(4^7 = 16384
)
- 각 경우마다 사용자 수 U = 100
에 대해 계산 →
O(U * E * 4^E)`
- 최악의 경우 163만 번 연산 → 충분히 해결 가능
6. 개선할 점 및 대체 방법
- 비트마스킹을 사용해 할인율 조합을 생성하는 방식도 가능