Level 2: 2023 KAKAO BLIND RECRUITMENT - 이모티콘 할인 행사, 중복 순열

참고 문서

• Programmers: 2023 KAKAO BLIND RECRUITMENT - 이모티콘 할인 행사

이 문서의 내용

• Step 1: 중복 순열로 할인율 방법 구하기
• Step 2: 문제에서 요구하는 최적의 수를 계산
• Step 3: 전체 코드

Step 1: 중복 순열로 할인율 방법 구하기

모든 상품이 할인되는 할인율 10% 20% 30% 40%에 대한 모든 케이스를 구합니다.

적용되는 모든 할인율을 구하기 위해 중복 순열을 사용합니다.

java

닫기

public void dupPermutation(int[] target, List<Integer> result, int remain)
{
‌if (0 == remain)
‌{
‌‌permutations.add(new ArrayList<>(result));
‌‌return;
‌}
‌
‌for (int i = 0; i < target.length; ++i)
‌{
‌‌result.add(target[i]);
‌‌dupPermutation(target, result, remain - 1);
‌‌result.remove(result.size() - 1);
‌}
}

static List<List<Integer>> permutations = new ArrayList<>();

코드		비고
Line 17	List<List<Integer>>  permutations	중복 순열 계산 결과입니다.  바깥쪽 컨테이너는 순열입니다. 안쪽 컨테이너는 순열을 구성하는 값에 대한 리스트입니다.

Step 2: 문제에서 요구하는 최적의 수를 계산

중복 순열을 순회하면서 문제에서 요구하는 최적의 수를 계산합니다.

• 이모티콘 플러스 서비스 가입자를 최대한으로 늘려야 합니다.
• 그 다음 목표는 이모티콘 판매액을 최대한으로 늘려야 합니다.
• 이때 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
• 이때 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

java

닫기

// 모든 경우의 수를 계산합니다.
List<Integer[]> answer = new ArrayList<>();
for (List<Integer> permutation : permutations)
{
‌// c: 이모티콘 플러스 서비스 가입, p: 이모티콘 구매 가격
‌int c = 0, p = 0;
‌for (int[] user : users)
‌{
‌‌int paid = 0;
‌‌for (int i = 0; i < permutation.size(); ++i)
‌‌{
‌‌‌int discount = permutation.get(i);
‌‌‌if (discount < user[0])
‌‌‌‌continue;
‌‌‌int discounted = (int) (emoticons[i] * (1.0f - (discount / 100.0f)));
‌‌‌paid += discounted;
‌‌}
‌‌‌‌
‌‌// 이모티콘 플러스 서비스에 가입합니다.
‌‌if (user[1] <= paid) ++c;
‌‌// 이모티콘 구매 가격을 누적시킵니다.
‌‌else p += paid;
‌}
‌‌‌
‌if (0 < c || 0 < p)
‌‌answer.add(new Integer[] { c, p });
}
‌‌
// 문제에서 요구하는 최적의 수를 0번 인덱스로 정렬합니다.
Collections.sort(answer, (lp, rp) -> {
‌if (lp[0] == rp[0]) {
‌‌return lp[1] < rp[1] ? 1 : (lp[1] > rp[1]) ? -1 : 0;
‌} else {
‌‌return lp[0] < rp[0] ? 1 : (lp[0] > rp[0]) ? -1 : 0;
‌}
});

return Arrays.stream(answer.get(0)).mapToInt(Integer::intValue).toArray();

코드		비고
Line 19:22	if (user[1] <= paid) ++c	이모티콘 플러스 서비스에 가입합니다.
	else p += paid	이모티콘 플러스 서비스에 가입하지 않았다면 구매 가격을 계산합니다.
Line 25:26	if (0 < c || 0 < p) answer.add(new Integer[] { c, p })	현재 순열에서의 계산 결과를 answer에 저장합니다.
Line 29:36	Collections.sort(...)	모든 결과 중 문제에서 요구하는 최적의 수를 0번 인덱스가 되도록 정렬합니다.
Line 38	answer.get(0)	모든 결과 중 문제에서 요구하는 최적의 수를 가져옵니다.
	mapToInt(Integer::intValue)	문제에서 요구하는 결과 타입과 일치하도록 Integer[]를 int[]로 캐스팅합니다.

Step 3: 전체 코드

각 단계별로 구성된 전체 코드는 다음을 참고합니다.

java

닫기

import java.util.*;
import java.util.Collections;

/**
 * 중복 순열을 구하고 문제에서 요구하는 최적의 수를 구합니다.
 * @see <a href="https://school.programmers.co.kr/learn/courses/30/lessons/150368">Programmers: 이모티콘 할인 행사</a>
​* @author namepgb
​*/
public class Solution
{
‌public void dupPermutation(int[] target, List<Integer> result, int remain)
‌{
‌‌if (0 == remain)
‌‌{
‌‌‌permutations.add(new ArrayList<>(result));
‌‌‌return;
‌‌}
‌‌
‌for (int i = 0; i < target.length; ++i)
‌‌{
‌‌‌result.add(target[i]);
‌‌‌dupPermutation(target, result, remain - 1);
‌‌‌result.remove(result.size() - 1);
‌‌}
‌}
‌
‌static List<List<Integer>> permutations = new ArrayList<>();
‌
‌public int[] solution(int[][] users, int[] emoticons)
‌{
‌‌int[] discounts = new int[] { 10, 20, 30, 40 };
‌‌// 중복 순열을 구합니다.
‌‌dupPermutation(discounts, new ArrayList<>(), emoticons.length);
‌‌
‌‌// 모든 경우의 수를 계산합니다.
‌‌List<Integer[]> answer = new ArrayList<>();
‌‌for (List<Integer> permutation : permutations)
‌‌{
‌‌‌// c: 이모티콘 플러스 서비스 가입, p: 이모티콘 구매 가격
‌‌‌int c = 0, p = 0;
‌‌‌for (int[] user : users)
‌‌‌{
‌‌‌‌int paid = 0;
‌‌‌‌for (int i = 0; i < permutation.size(); ++i)
‌‌‌‌{
‌‌‌‌‌int discount = permutation.get(i);
‌‌‌‌‌if (discount < user[0])
‌‌‌‌‌‌continue;
‌‌‌‌‌int discounted = (int) (emoticons[i] * (1.0f - (discount / 100.0f)));
‌‌‌‌‌paid += discounted;
‌‌‌‌}
‌‌‌‌
‌‌‌‌// 이모티콘 플러스 서비스에 가입합니다.
‌‌‌‌if (user[1] <= paid) ++c;
‌‌‌‌// 이모티콘 구매 가격을 누적시킵니다.
‌‌‌‌else p += paid;
‌‌‌}
‌‌‌
‌‌‌if (0 < c || 0 < p)
‌‌‌‌answer.add(new Integer[] { c, p });
‌‌}
‌‌
‌‌// 문제에서 요구하는 최적의 수를 0번 인덱스로 정렬합니다.
‌‌Collections.sort(answer, (lp, rp) -> {
‌‌‌if (lp[0] == rp[0]) {
‌‌‌‌return lp[1] < rp[1] ? 1 : (lp[1] > rp[1]) ? -1 : 0;
‌‌‌} else {
‌‌‌‌return lp[0] < rp[0] ? 1 : (lp[0] > rp[0]) ? -1 : 0;
‌‌‌}
‌‌});

‌‌return Arrays.stream(answer.get(0)).mapToInt(Integer::intValue).toArray();
‌}
}