Hash Tables: Ice Cream Parlor 풀이 java

Hash Tables: Ice Cream Parlor | HackerRank

 

포인트는 카테고리에 있는 것처럼 HashTable (HashMap)!

 

1. cost 값들을 HashMap에 저장하고

2. for : cost 값을 하나씩 가지고 오며 money-cost 값을 구함

3. money-cost 값이 hashmap에 있는지 확인하고, 있으면 return

 

이렇게 하면 O(n)의 시간복잡도를 가져서 시간초과가 안남

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'whatFlavors' function below.
     *
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY cost
     *  2. INTEGER money
     */

    public static void whatFlavors(List<Integer> cost, int money) {
        // Write your code here

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        int size = cost.size();

        for (int i = 0; i < size; i++) {
            map.put(cost.get(i), i + 1);
        }

        for (int i = 0; i < size; i++) {
            int f = cost.get(i);
            int k = money - f;
            
            if (map.containsKey(k)) {
                int val = map.get(k);
                if(val != i+1){
                System.out.println(i+1 + " " + val);
                return;
                }
            }
        }
    }
}