티켓 전략 게임

얼마 전, 모두 알만한 회사에 코딩테스트를 봤다.
120분에 1문제를 풀면 되는 테스트로 난이도가 꽤 있을 거라 생각하고 준비했지만 결국 풀지 못했다.
테스트가 끝나고 나서도 하루 종일 어떻게 풀어야 할지 고민했던 거 같다.
다음 날 저녁, 불현듯 어떻게 풀어야 할지 떠오르면서 아쉬움이 밀려와 잠을 설쳤다. 아침에 눈뜨자마자 노트북을 열고 다시 문제를 풀어보았다. 생각해 보면 그렇게 어려운 문제도 아니었는데 긴장했었나 싶다. 아쉬운 마음에 블로그에 코드라고 남겨본다.
어제 실패했으니 내일의 성공 확률은 더 높아졌을 거라 생각한다.
 

import java.util.*;

public class Solution {

    public int solution(String[] tickets, int roll, String[][] shop, int money) {
        int answer = 0;

        // 티켓의 가격 맵
        Map<String, Integer> priceMap = new HashMap<>();
        for (String ticket : tickets) {
            String[] s = ticket.split(" ");
            priceMap.put(s[0], Integer.valueOf(s[1]));
        }

        // 샵 i 개를 사용했을 때 구매할 수 있는 티켓의 개수
        Map<String, Integer>[] ticketsDp = new Map[shop.length];
        Map<String, Integer> shopZero = new HashMap<>();
        for (String t : shop[0]) {
            shopZero.merge(t, 1, Integer::sum);
        }
        ticketsDp[0] = shopZero;
        for (int i = 1; i < shop.length; i++) {
            Map<String, Integer> previous = new HashMap<>(ticketsDp[i - 1]);
            for (String t : shop[i]) {
                previous.merge(t, 1, Integer::sum);
            }
            ticketsDp[i] = previous;
        }

        // 샵 i개를 이용했을 때 만들 수 있는 골드 티켓 카운트
        for (int i = 0; i < ticketsDp.length; i++) {
            // 새로고침 비용만큼 차감
            int canUseMoney = money - roll * i;
            if(canUseMoney <= 0) break;
            int goldTicketCnt = 0;
            Map<String, Integer> ticketsCntMap = ticketsDp[i];

            for (Map.Entry<String, Integer> entry : ticketsCntMap.entrySet()) {
                String ticketName = entry.getKey();
                Integer ticketCount = entry.getValue();
                Integer ticketPrice = priceMap.get(ticketName);

                if (ticketCount >= 3 && ticketPrice * 3 <= canUseMoney) {
                    canUseMoney -= ticketPrice * 3;
                    ticketsCntMap.put(ticketName, ticketCount - 3);
                    goldTicketCnt++;
                }
            }

            answer = Math.max(answer, goldTicketCnt);
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();

        // Test case 1
        var t1 = new String[]{"A 1", "B 2", "C 5", "D 3"};
        var r1 = 10;
        var s1 = new String[][]{
                {"B", "C", "B", "C"},
                {"A", "A", "A", "B"},
                {"D", "D", "C", "D"}
        };
        var m1 = 30;
        System.out.println(T.solution(t1, r1, s1, m1) == 2);

        // Test case 2
        var t2 = new String[]{"A 1", "B 2", "C 5", "D 3"};
        var r2 = 10;
        var s2 = new String[][]{
                {"B", "C", "B", "C"},
                {"A", "A", "A", "B"},
                {"D", "D", "C", "D"}
        };
        var m2 = 100;
        System.out.println(T.solution(t2, r2, s2, m2) == 4);

        // Test case 3
        var t3 = new String[]{"A 2", "B 1"};
        var r3 = 5;
        var s3 = new String[][]{
                {"A", "A", "A"},
                {"A", "B", "B"},
                {"A", "B", "B"},
                {"A", "B", "B"}
        };
        var m3 = 19;
        System.out.println(T.solution(t3, r3, s3, m3) == 2);
    }
}