Hash HackerRank Algorithms in Java ‘Ice Cream Parlor’ solution

Problem

Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool their money to buy ice cream. On any given day, the parlor offers a line of flavors. Each flavor has a cost associated with it. Given the value of money and the cost of each flavor for t trips to the Ice Cream Parlor, help Sunny and Johnny choose two distinct flavors such that they spend their entire pool of money during each visit. ID numbers are the 1- based index number associated with a cost. For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second. For example, there are n = 5 flavors having cost = [2,1,3,5,6]. Together they have money = 5 to spend. They would purchase flavor ID’s 1 and 3 for a cost of 2 + 3 = 5. Use 1 based indexing for your response.

• Two ice creams having unique IDs and may have the same cost.
• There will always be a unique solution.

Sample Input

2
4
5
1 4 5 3 2
4
4
2 2 4 3

Sample Output

1 4
1 2

Solution

생각보다 어려웠고 생각보다 단순했다.

• key값으로 유니크한 id를 하려했으나, value간의 연산을 하기 너무 힘들어 아이스크림 값을 key 값으로 한다.
• 가지고 있는 돈에서 i번째 아이스크림의 값을 뺀 나머지가 이미 맵에 있다면, 그 아이스크림과 i번째 아이스크림을 사면 예산을 다 사용하는 경우가 된다.
• 단, 예제처럼 두 아이스크림의 값이 같은 경우가 생기는데 (2, 2 그런데 가지고 있는 돈도 4라서 4-2=2 는 벌써 가지고 있다.) 그래서 if(parlor.containsKey(money - cost[i])) 이거를 먼저 비교해주면 된다.

Code

    // Complete the whatFlavors function below.
    static void whatFlavors(int[] cost, int money) {
        Map<Integer, Integer> parlor = new LinkedHashMap<>();    
        for(int i = 0; i < cost.length; i++) {
            if(cost[i] < money) {
                if(parlor.containsKey(money - cost[i])) {
                    System.out.println((parlor.get(money - cost[i])+1) + " " + (i+1));
                    return;
                }
                
                if(!parlor.containsKey(cost[i])) parlor.put(cost[i], i);
            }
        }
    }