[Mock] Amazon 4

836. Rectangle Overlap

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

My Answer 1: Accepted (Runtime: 32 ms - 61.42% / Memory Usage: 14.4 MB - 16.84%)

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # 애초에 rec1, rec2 가 사각형이 아닌 직선이 될 경우 => False
        if rec1[0] == rec1[2] or rec1[1] == rec1[3] or rec2[0] == rec2[2] or rec2[1] == rec2[3]:
            return False
        # overlap 되지 않고 나란히 붙기만 할 경우 => False
        if rec1[0] == rec2[2] or rec1[1] == rec2[3] or rec1[2] == rec2[0] or rec1[3] == rec2[1]:
            return False
        
        # rec2 의 (x1, y1) 이 rec1 에 들어갈 경우
        if rec1[0] <= rec2[0] < rec1[2] and rec1[1] <= rec2[1] < rec1[3]:
            return True
        # rec2 의 (x2, y2) 가 rec1 에 들어갈 경우
        elif rec1[0] <= rec2[2] <= rec1[2] and rec1[1] <= rec2[3] <= rec1[3]:
            return True
        # rec2 의 x1 과 y2 가 rec1 에 들어갈 경우
        elif rec1[0] <= rec2[0] < rec1[2] and rec1[1] <= rec2[3] <= rec1[3]:
            return True
        # rec2 의 x2 와 y1 이 rec1 에 들어갈 경우
        elif rec1[0] <= rec2[2] <= rec1[2] and rec1[1] <= rec2[1] <= rec1[3]:
            return True
        # rec2 의 x 들은 rec1 의 바깥에 있고 y 중에 하나는 rec1 안에 있을 경우
        elif (rec2[0] < rec1[0] and rec1[2] <= rec2[2]) and (rec1[1] <= rec2[1] < rec1[3] or rec1[1] <= rec2[3] < rec1[3]):
            return True
        # rec2 의 y 들은 rec1 의 바깥에 있고 x 중에 하나는 rec1 안에 있을 경우
        elif (rec2[1] < rec1[1] and rec1[3] <= rec2[3]) and (rec1[0] <= rec2[0] < rec1[2] or rec1[0] <= rec2[2] < rec1[2]):
            return True
        # rec2 의 x, y 모두 rec1 을 벗어날 경우
        elif (rec2[0] < rec1[0] and rec1[2] <= rec2[2]) and (rec2[1] < rec1[1] and rec1[3] <= rec2[3]):
            return True
        else:
            return False

모든 경우를 다 찾아서... 끔찍하게 풀어봤읍니다

---

763. Partition Labels

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

My Answer 1: Accepted (Runtime: 40 ms - 68.82% / Memory Usage: 14.1 MB - 94.51%)

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        result = []
        
        while S:
            i = 0
            cut = S.rindex(S[0])
            while i < cut:
                cut = max(cut, S.rindex(S[i]))
                i += 1
            result.append(cut+1)
            S = S[cut+1:]
        
        return result

우선 S[0] 의 중복된 문자 중 가장 마지막에 나타나는 index (rindex) 를 cut 으로 잡고
[0 ~ cut] 까지를 훑어보면서 각 문자마다 제일 끝쪽에 나타나는 중복값 index 로 cut 을 update

[0 ~ cut] 까지는 한 묶음이 되므로 잘라준다 => S = S[cut+1:]

계속 반복하기~