📄 문제
프로그래머스 > 2023 KAKAO BLIND RECRUITMENT > 이모티콘 할인행사
구현해야 하는 것은
이모티콘 종류와 유저들의 구입 정보가 주어졌을 때, 이모티콘 플러스 가입자와 이모티콘 판매액을 최대로 늘리는 경우를 구해야 한다.
여기서 중요한 것은 목표의 우선순위다.
- 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
- 이모티콘 판매액을 최대한 늘리는 것.
이모티콘 플러스 가입자가 3명, 판매액이 10,000원보다 이모티콘 플러스 가입자가 5명, 판매액이 0원이 목표에 부합한다.
각 이모티콘의 할인율이 다를 수 있으므로 어떤 이모티콘을 얼마나 할인해줘야 가입자 수와 매출을 극대화시킬 수 있을지 알기 위해서는 각 이모티콘마다 10%, 20%, 30%, 40% 할인율을 다 적용해본 모든 경우의 수를 다 구해봐야 한다.
다행히 제한사항을 살펴보면 이모티콘의 종류는 최대 7개다. 모든 경우의 수를 구해도 최대 47(=16384)이다. 완전 탐색으로 모든 경우를 구하기 충분하다.
❗️ 여기서 경우의 수가 최대 47(=16384)라는 것은 할인율을 조합한 경우의 수다. 아래에서 설명하듯 할인율 조합 내에서도 사용자, 이모티콘을 순회하므로 전체 코드 내 반복 횟수가 47(=16384)는 아니다.
0️⃣ 구조 확인하기
큰 틀은 다음과 같다.
순회문은 3번 중첩되어 있다. 가장 외부 반복문은 할인율을 조합한 모든 경우의 수를 순회하기 위함이다. 그 다음으로는 모든 사용자를 순회하고 가장 내부에서 모든 이모티콘을 순회한다.
- 🔁 할인율 조합별 이모티콘 플러스 가입자와 판매액을 알기 위해 모든 할인율 조합 경우의 수를 순회한다.
- 🔁 사용자별 이모티콘 구매 정보를 알기 위해 모든 사용자를 순회한다.
- 🔁 할인율이 적용된 각 이모티콘의 구매 여부와 구매 금액을 알기 위해 모든 이모티콘을 순회한다.
- 🔁 사용자별 이모티콘 구매 정보를 알기 위해 모든 사용자를 순회한다.
1️⃣ 중복순열을 이용해 모든 경우의 수를 구한다.
경우의 수를 구하기 위해서 주의해야 하는 점은 아래 두 가지다.
- 10,20,30,40이라는 네 개의 숫자를 순서를 고려해서 이모티콘의 갯수만큼 뽑아내야 한다.
(이모티콘 A,B가 있을 때 [A 할인율(10), B 할인율(20)]와 [A 할인율(20), B 할인율(10)]는 다르다.)
- 모든 이모티콘의 할인율이 동일한 경우도 있다. 그러므로 자기 자신의 중복도 허용해야 한다.
(이모티콘 A,B가 있을 때 [A 할인율(10), B 할인율(10)]일 수 있다.)
조건 1,2에 따라 중복 순열로 구하기로 했다.
이모티콘이 3개(A, B, C)라면 [A 할인율(10), B 할인율(10), C 할인율(10)]부터 [A 할인율(40), B 할인율(40), C 할인율(40)]까지 총 64개의 경우의 수를 얻을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const getPermutations = (arr, length) => {
const result = [];
if (length === 1) return arr.map((v) => [v]);
arr.forEach((fixed, index, origin) => {
const permutations = getPermutations(origin, length - 1);
const attached = permutations.map((res) => [fixed, ...res]);
result.push(...attached);
});
return result;
};
// 👇 EX) 1, 2, 3 중에 2개를 선택하는 경우
getPermutations([1, 2, 3], 2); // (9) [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]
2️⃣ 이모티콘을 할인할 수 있는 모든 경우의 수를 구하고 사용자가 어떤 경우에 이모티콘을 구매할지, 구매한다면 구매 비용은 얼마인지 구해야 한다.
1️⃣에서 생성한 getPermutations를 이용해서 이모티콘을 할인하는 경우의 수를 구해야 한다. 각 경우의 수는 이모티콘의 갯수만큼의 요소를 가진 배열 형태다.
이모티콘(emoticons)이 [7000,3000,2000,1000,5000]로 주어진다면 getPermutations가 반환하는 2차원 배열의 각 요소는 할인율을 5개 뽑아낸 경우로 이모티콘의 갯수와 무조건 같다. [10,20,30,40,10]의 형태로 주어지고, 이는 첫 번째 이모티콘(7000)은 10% 할인, 두 번째 이모티콘(3000)은 20%, 세 번째 이모티콘(2000)은 30%, 네 번째 이모티콘(1000)은 40% 할인, 다섯 번째 이모티콘(5000)은 10% 할인한다는 의미다.
1
2
3
4
5
// 🔁 할인율 조합별 이모티콘 플러스 가입자와 판매액을 알기 위해 모든 할인율 조합 경우의 수를 순회한다.
getPermutations([10, 20, 30, 40], emoticons.length).forEach((permutation) => {
// permutation : 할인율을 조합한 특정 경우의 수를 담은 배열이다. 이 배열의 길이는 무조건 이모티콘 갯수와 같다. (permutation.length === emoticons.length)
// permutation[i]는 emoticons[i]의 할인율이다.
});
각 경우의 수마다 이모티콘 플러스 가입자와 판매 금액을 계산해야 한다.
1
2
3
4
5
6
7
getPermutations([10, 20, 30, 40], emoticons.length).forEach((permutation) => {
// 👇 permutation의 이모티콘 플러스 가입자 수를 누적하기 위한 변수
let plusUser = 0;
// 👇 permutation의 이모티콘 판매액을 누적하기 위한 변수
let sales = 0;
});
이제 사용자가 어떤 이모티콘을 구매할지 찾아야 한다. 사용자마다 원하는 할인율 기준이 다르기 때문에 모든 사용자가 모든 이모티콘을 확인해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
getPermutations([10, 20, 30, 40], emoticons.length).forEach((permutation) => {
let plusUser = 0;
let sales = 0;
// 🔁 사용자별 이모티콘 구매 정보를 알기 위해 모든 사용자를 순회한다.
users.forEach((user) => {
// 👇 rate : 현재 사용자가 원하는 최소 이모티콘 할인율
// 👇 total : 현재 사용자가 이모티콘 플러스 가입하기로 한 최소 금액
const [rate, total] = user;
// 할인율 기준에 부합하여 이모티콘을 구매할 때 구매 금액을 누적하기 위한 변수.
let tempAmount = 0;
// 🔁 할인율이 적용된 각 이모티콘의 구매 여부와 구매 금액을 알기 위해 모든 이모티콘을 순회한다.
emoticons.forEach((emoticon, index) => {
// 현재 이모티콘의 할인율이 사용자가 원하는 할인율과 같거나 커야 구매한다.
if (permutation[index] >= rate) {
// 이모티콘을 구매한다면 할인율을 적용한 금액을 tempAmount에 누적한다.
// 10,20,30,40은 할인율이므로 100에서 할인율을 뺀 값의 백분율로 계산해야 한다.
tempAmount += emoticon * ((100 - permutation[index]) / 100);
}
});
// 한 사용자에 대해 모든 이모티콘을 확인했으므로 tempAmount은 현재 유저가 구매한 이모티콘의 총 금액이다.
// total과 같거나 크면 이모티콘 플러스 서비스에 가입자 수에 누적한다.
if (tempAmount >= total) {
plusUser++;
} else {
// 이모티콘 플러스 서비스 가입 조건에 부합하지 않는다면 총 매출액에 누적한다.
sales += tempAmount;
}
});
});
3️⃣ 가장 목적에 부합하는 값을 찾기 위해 모든 경우의 수마다 얻어낸 plusUser와 sales를 임시 객체 담아둔다.
이제 경우의 수마다 이모티콘 플러스 가입자 수(plusUser)와 이모티콘 매출액(sales)를 알고 있다. 모든 경우의 수에 대해 plusUser와 sales를 임시 객체 obj에 담아둔다.
최우선 순위는 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것이다. 그러므로 plusUser 중 최대값을 찾아야 한다. plusUser의 최댓값이 여러 개 존재하면 그 중 sales가 가장 큰 값을 찾아내는 것이 목적을 최대한으로 달성하는 것이다.
plusUser를 obj의 key로 설정하고 value로 빈 배열로 초기화한 뒤에 sales를 이 배열에 쌓아두고 모든 순회가 종료된 후 각각의 최대값을 찾아서 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const solution = (users, emoticons) => {
const obj = {};
getPermutations([10, 20, 30, 40], emoticons.length).forEach((permutation) => {
let plusUser = 0;
let sales = 0;
users.forEach((user) => {
// ...
});
// 이모티콘 플러스 가입자 수가 가장 큰 값을 얻어야 하므로 가입자 수를 key로 지정하고 빈 배열로 초기화한다.
if (!obj[plusUser]) {
obj[plusUser] = [];
}
// 이모티콘 플러스 가입자 수가 동일하고 매출액은 다를 수 있으므로 매출액은 배열의 요소로 쌓아둔다.
obj[plusUser].push(sales);
});
let maxPlusUser = 0;
let maxSales = 0;
//Math.max로 obj의 key 중 최대값을 얻는다. 이모티콘 플러스 서비스 가입자를 최대한 늘린 경우인 것이다.
Object.keys(obj).forEach((key) => {
maxPlusUser = Math.max(maxPlusUser, key);
});
//이모티콘 플러스 서비스 가입자가 가장 많다면 그 다음으로 매출액이 커야 한다. 그러므로 obj[key] 배열에서 최대값을 찾아야 한다.
maxSales = Math.max(...obj[maxPlusUser]);
return [maxPlusUser, maxSales];
};
🏹 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const solution = (users, emoticons) => {
const obj = {};
getPermutations([10, 20, 30, 40], emoticons.length).forEach((permutation) => {
let plusUser = 0;
let sales = 0;
users.forEach((user) => {
const [rate, total] = user;
let tempAmount = 0;
emoticons.forEach((emoticon, index) => {
if (permutation[index] >= rate) {
tempAmount += emoticon * ((100 - permutation[index]) / 100);
}
});
if (tempAmount >= total) {
plusUser++;
} else {
sales += tempAmount;
}
});
if (!obj[plusUser]) {
obj[plusUser] = [];
}
obj[plusUser].push(sales);
});
let maxPlusUser = 0;
let maxSales = 0;
Object.keys(obj).forEach((key) => {
maxPlusUser = Math.max(maxPlusUser, key);
});
maxSales = Math.max(...obj[maxPlusUser]);
return [maxPlusUser, maxSales];
};
const getPermutations = (arr, length) => {
const result = [];
if (length === 1) return arr.map((v) => [v]);
arr.forEach((fixed, index, origin) => {
const permutations = getPermutations(origin, length - 1);
const attached = permutations.map((res) => [fixed, ...res]);
result.push(...attached);
});
return result;
};
⛳️ 더 좋은 해결책
할인율을 각기 다르게 조합하는 모든 경우의 수를 구하기 위해서 이전에 조합을 구하는 코드를 참고하여 중복순열을 사용했다. 다른 답안을 보니 더 간단한게 경우의 수를 구하는 방법이 다양했다. 좋은 방법인거 같아서 기록해둔다.
프로그래머스 skyshr님의 코드
🐝 참고