Mock Interview: Amazon #2

Relative Sort Array

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //Arrays.sort(arr1);
        
        List<Integer> a = new ArrayList<Integer>();
        
        Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
        
        for (int i = 0; i < arr1.length; i++) {
            m.put(arr1[i], m.getOrDefault(arr1[i], 0) + 1);
        }
        
        
        for (int j = 0; j < arr2.length; j++) {
            for (int k = 0; k < m.get(arr2[j]); k++) {
                a.add(arr2[j]);
            }
            m.remove(arr2[j]);
        }
        
        
        for (Integer key : m.keySet()) {
            for (int l = 0; l < m.get(key); l++) {
                a.add(key);
            }
        }
        
        return a.stream().mapToInt(i->i).toArray();  
    }
}

Runtime: 6 ms, faster than 14.39% of Java online submissions for Relative Sort Array.
Memory Usage: 39.2 MB, less than 54.05% of Java online submissions for Relative Sort Array.

처음에는 쉬맵이로 했는데 뭔 이유에서인지 마지막에 순서가 sort가 안됨.. 그 전에 sort 하는데 왜그러는지 모르겠읍니다;
그래서 treemap으로 했더니 런타임이 믿기지 않아서 파이선으로도 풀었어요

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        arr1.sort();
        
        result = []
        
        m = {}
        
        for x in arr2:
            m = arr1.count(x)
            for i in range(m):
                result.append(x)
                arr1.remove(x)
        
        return result + arr1

Runtime: 44 ms, faster than 38.19% of Python3 online submissions for Relative Sort Array.
Memory Usage: 14.3 MB, less than 88.63% of Python3 online submissions for Relative Sort Array.

조금 더 빠름..
새삼 파이선이 data structure 오락가락 하기 쉽네요^^...

Number of Dice Rolls with Target Sum

전에 풀었던 문제..

class Solution {
    int MOD = 1000000000 + 7;
    Map<String, Integer> memo = new HashMap<>();
    public int numRollsToTarget(int d, int f, int target) {
        if (d == 0 && target == 0) {
            return 1;
        }
        if (target > d * f || d > target) {
            return 0;
        }
        String str = d + " " + target;
        if (memo.containsKey(str)) {
            return memo.get(str);
        }
        int res = 0;
        for (int i = 1; i <= f; i++) {
            if (target >= i) {
                res = (res + numRollsToTarget(d - 1, f, target - i)) % MOD;
            } else {
                break;
            }
        }
        memo.put(str, res);
        return res;
    }
}

Runtime: 44 ms, faster than 36.55% of Java online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 40.2 MB, less than 21.10% of Java online submissions for Number of Dice Rolls With Target Sum.

사실.... 루션이 있길래 살짝 봤읍니다..ㅎ
그래도 이제는 100% 이해했읍니다^^
냅다외워~