[Mock] Amazon 6

1331. Rank Transform of an Array

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

• Rank is an integer starting from 1.
• The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
• Rank should be as small as possible.

My Answer 1: Accepted (Runtime: 352 ms - 56.35% / Memory Usage: 31.6 MB - 90.02%)

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        arr2 = sorted(arr)
        rank = {}
        
        r = 1
        now = float('inf')
        for i in range(len(arr2)):
            if arr2[i] != now:
                now = arr2[i]
                rank[arr2[i]] = r
                r += 1
        
        result = []
        for i in range(len(arr)):
            result.append(rank[arr[i]])
            
        return result

arr 를 정렬한 arr2 를 만들고 rank 딕셔너리를 만들어서 각 숫자마다 순위를 정해줬다

중복이 아닐 경우에만 rank 에 r 값을 넣어줌
r 은 1 부터 시작

---

1214. Two Sum BSTs

Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

My Answer 1: Accepted (Runtime: 120 ms - 30.28% / Memory Usage: 17 MB - 88.62%)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        queue = [root1]
        
        while queue:
            root = queue.pop(0)
            if root:
                # 마이너스도 있어서 모든 숫자마다 확인해줘야 하는듯...
                if self.find(root2, target - root.val):
                    return True
                if root.left:
                    queue.append(root.left)
                if root.right:
                    queue.append(root.right)
        
        return False
        
    def find(self, root2, num):
        queue = [root2]

        while queue:
            root = queue.pop(0)
            if root:
                if root.val == num:
                    return True
                if root.left and root.val > num:
                    queue.append(root.left)
                if root.right and root.val < num:
                    queue.append(root.right)

        return False

두 트리 모두 싹 훑어서 숫자들을 따로 리스트로 빼낸 다음
two sum 쓰는 무식한 방법이 가장 먼저 떠올랐네요..^^

근데 이거도... 훌륭한 코드는 아닌 듯...ㅎ

root1 을 level order 로 둘러보면서 find(root2, target - root.val) 해줌
=> root1 의 값 하나를 잡고 target - val 값을 root2 에서 찾는 것

bst 니까 find 에서는 찾을 값이 val 보다 작으면 왼쪽으로, 크면 오른쪽으로 가는 조건 추가

좀 더 빠르게 하기 위해 root1 을 볼때도 조건을 추가해줄까 했는데
숫자가 음수도 포함되어있어서 무조건 다 훑어봐야하는듯

---

두 문제 다 더 빠르게 할 방법이 잘 안 떠오르네요...^^