Mock Interview: Amazon

1351. Count Negative Numbers in a Sorted Matrix

class Solution {
    public int countNegatives(int[][] grid) {
        int total = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] < 0) {
                    total++;
                }
            }
        }
        
        return total;
    }
}

RG?^^

Runtime: 1 ms, faster than 46.91% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
Memory Usage: 39.6 MB, less than 34.12% of Java online submissions for Count Negative Numbers in a Sorted Matrix.

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        x = len(grid) - 1
        y = 0
        num = 0
        c = 0
        while x >= 0 and c < len(grid[0]):
            if grid[x][c] < 0:
                num = num + len(grid[0]) - c
                x = x - 1
            else:
                c += 1
        return num

Runtime: 112 ms, faster than 92.67% of Python3 online submissions for Count Negative Numbers in a Sorted Matrix.
Memory Usage: 15.1 MB, less than 45.52% of Python3 online submissions for Count Negative Numbers in a Sorted Matrix.

중간에 끊는 방식~~
만약 < 0 인게 나오면 그 아래로는 다 <0 이니 그만큼 더해주는 방식입니다

1382. Balance a Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<TreeNode> tree = new ArrayList<TreeNode>();
    public TreeNode balanceBST(TreeNode root) {
        getValues(root);   
        
        return bst(0, tree.size() - 1);
        
    }
    
    private void getValues(TreeNode root) {
        if (root == null) {
            return;
        }
        
        getValues(root.left);
        tree.add(root);
        getValues(root.right);
    }
    
    private TreeNode bst(int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = tree.get(mid);
        
        root.left = bst(start, mid - 1);
        root.right = bst(mid + 1, end);
        
        return root; 
        
    }  
}

Runtime: 2 ms, faster than 99.62% of Java online submissions for Balance a Binary Search Tree.
Memory Usage: 40.9 MB, less than 96.71% of Java online submissions for Balance a Binary Search Tree.

처음에는 죄다 arraylist에 넣어준 다음에 (이미 sorted 되어있으니 inorder로)
그 다음에 sorted array to balanced bst라는 아름다운 포스트가 있어서

https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/

이거 고대로 따라했읍니다^^
계속 중간 친구들만 빼내면 돼요

1478. Allocate Mailboxes

class Solution {
    int MAX = 10000000;

    public int minDistance(int[] houses, int k) {
        int n = houses.length;
        Arrays.sort(houses);
        int[][] dp = new int[n][k];
        int[][] cost = new int[n][n];
		
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int median = houses[(i + j) / 2];
                int sum = 0;
                for (int l = i; l <= j; ++l) {
                    sum += Math.abs(median - houses[l]);
                }
                cost[i][j] = sum;
            }
        }
        for (int i = 0; i < n; ++i) Arrays.fill(dp[i], -1);
        return solve(houses, k, 0, 0, dp, cost);
    }

    public int solve(int[] houses, int k, int pos, int curK, int[][] dp, int[][] cost) {
        if (pos == houses.length) {
            if (curK == k) {
                return 0;
            }
            return MAX;
        }
        if (curK == k) return MAX;
        if (dp[pos][curK] != -1) return dp[pos][curK];

        int answer = MAX;
        for (int i = pos; i < houses.length; ++i) {
            answer = Math.min(answer, solve(houses, k, i + 1, curK + 1, dp, cost) + cost[pos][i]);
        }

        dp[pos][curK] = answer;
        return answer;
    }
}

Runtime: 9 ms, faster than 87.85% of Java online submissions for Allocate Mailboxes.
Memory Usage: 38.3 MB, less than 56.21% of Java online submissions for Allocate Mailboxes.

house median 이 언제나 제일 좋은 거리라는데 어케 생각하시나요...
읽으면 읽을수록 모르겠어욥;;