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

참고 문서

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

이 문서의 내용

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

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

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

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: 문제에서 요구하는 최적의 수를 계산

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

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

// 모든 경우의 수를 계산합니다.
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: 전체 코드

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

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();
	}
}