C# 이모티콘 할인행사 - DFS / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/150368

 

 

나의 풀이

public class User
{
    public int ratio;
    public int over;
}

public class Emoticon
{
    public int originPrice;
    public int saleRatio; // 10, 20, 30, 40
    public int GetSalePrice() => originPrice * (100 - saleRatio) / 100;
}

public int[] solution(int[,] users, int[] emoticons) 
{
    User[] arr = Enumerable.Range(0, users.GetLength(0))
                        .Select(s => new User{ ratio = users[s, 0], over = users[s, 1] })
                        .ToArray();

    Emoticon[] emo = emoticons.Select(s => new Emoticon{ originPrice = s })
                              .ToArray();

    int plusCount = 0;
    int sales = 0;
    DFS(0, arr, emo, ref plusCount, ref sales);
    return new int[2] { plusCount, sales };
}

void DFS(int index, User[] users, Emoticon[] emo, ref int plusCount, ref int sales)
{
    if(index == emo.Length)
    {
        int curPlusCount = 0;
        int curSales = 0;
        foreach(User user in users)
        {
            int userSpendMoney = emo.Where(w => w.saleRatio >= user.ratio)
                                   .Select(s => s.GetSalePrice())
                                   .Sum();

            if(userSpendMoney >= user.over) 
                ++curPlusCount;
            else 
                curSales += userSpendMoney;
        }

        if(plusCount < curPlusCount)
        {
            plusCount = curPlusCount;
            sales = curSales;
        }
        else if(plusCount == curPlusCount)
        {
            if(sales < curSales)
                sales = curSales;
        }

        return;
    }

    for(int k = 10; k <= 40; k += 10) // 할인 폭은 10% ~ 40% 고정임
    {
        emo[index].saleRatio = k; // 할인
        DFS(index + 1, users, emo, ref plusCount, ref sales);
    }
}

1.

할인 폭은 10%, 20%, 30%, 40%로 고정이고 유저는 ~100명, 이모티콘 ~7개 의 조건으로

컬렉션의 수가 적어 대놓고 완전탐색으로 풀라고 유도하고 있다.

 

2.

문제 자체는 어렵지 않지만 부가적으로 붙는 조건들이 많기 때문에

Tuple 타입만으로 풀기에는 코드가 복잡해진다. 별도로 데이터 컨테이너 클래스를 선언하고 풀이하는 것이 좋다.

 

3.

지문 중 함정으로 금액을 넘어가면 전부 환불하고~라는 대목이 있는데,

랭킹방식으로 구매하는 거면 구매한 뒤에 밀리는 것들을 환불하는 로직이 들어가지만

전체합을 기준으로 살지 말지를 결정하기 때문에 개별적으로 처리하지 않아도 된다.