[파이썬/Python] Leet Code 3000(Easy): Maximum Area of Longest Diagonal Rectangle

숨·2025년 8월 26일

알고리즘 문제 풀이

목록 보기

121/128

📌 문제 : Leet Code 3000

📌 문제 탐색하기

dimensions : 인덱스가 0부터 시작하는 2차원 배열 ( $1 ≤ dimensions.length ≤ 100$ )
dimensions[i][0], dimensions[i][1] : 2차원 배열 내 저장된 정수 ( $1 ≤ dimensions[i][0], dimensions[i][1] ≤ 100$ )

문제 풀이

입력된 2차원 배열 dimensions엔 직사각형의 (길이, 너비)가 저장되어 있다.
이를 활용해 대각선 길이를 구하고 가장 큰 대각선 길이를 가지는 직사각형의 넓이를 반환하며, 동일한 대각선 길이가 있을 경우 가장 큰 넓이를 반환하는 문제이다.

대각선 길이는 피타고라스 정의에 의해 구할 수 있고 넓이는 길이와 너비를 곱해서 구할 수 있다.
→ for문을 통해 dimensions의 요소에 하나씩 접근하여 대각선 길이와 넓이를 계산하고 이를 리스트에 추가한다.

정렬에 대각선 길이 순, 넓이 순이라는 2가지 조건이 붙기 때문에 lambda를 활용해 2개의 우선순위에 따라 정렬하도록 구현한다.
그렇게 정렬된 리스트의 가장 첫번째 값을 반환하면 원하는 결과를 얻을 수 있다.

가능한 시간복잡도

for문으로 대각선 길이와 넓이 계산 → $O(n)$
리스트 정렬 → $O(n log n)$

최종 시간복잡도
최악의 경우 $O(n log n) = O(100 * log(100))$ 이므로 충분히 동작할 수 있다.

알고리즘 선택

for문으로 계산 후 리스트 내림차순 정렬

📌 코드 설계하기

대각선 길이, 넓이 저장할 리스트 정의
대각선 길이, 넓이 구하기
내림차순 정렬 (1순위 : 대각선, 2순위 : 넓이)

📌 시도 회차 수정 사항

1회차

lambda와 sort() 함수로 정렬할 때 일반 sort() 함수 사용할 때처럼 reverse=True 옵션을 넣었는데 동작하지 않았다.
다중 조건을 통한 복합 정렬 시 복수 조건 각각을 독립적으로 제어하기 위해 각 요소에 -를 붙이는 식으로 내림차순 옵션을 지정하기 때문이다.

📌 정답 코드

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        # 대각선 길이, 넓이 저장할 리스트 정의
        calculate_list = [[] for _ in range(len(dimensions))]

        # 대각선 길이, 넓이 구하기
        for i in range(len(dimensions)):
            i_diagonal = sqrt(((dimensions[i][0])**2 + (dimensions[i][1])**2))
            i_area = dimensions[i][0] * dimensions[i][1]
            calculate_list[i] = (i_diagonal, i_area)

        # 내림차순 (1순위 : 대각선, 2순위 : 넓이)
        calculate_list.sort(key=lambda x: (-x[0], -x[1]))

        return calculate_list[0][1]

결과

👍 다른 풀이

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        # 대각선 최대 길이(제곱값)와 결과 넓이 변수 초기화
        max_diag = 0
        res = 0
        
        # 모든 사각형에 대해 반복
        for a, b in dimensions:
            diag = a**2 + b**2  # 해당 사각형의 대각선 제곱값을 계산
            
            # 대각선이 더 크면 최대값 및 넓이를 새로 기록
            if diag > max_diag:
                max_diag = diag
                res = a * b
                
            # 대각선이 최대값과 같으면 넓이만 비교해 더 큰 쪽으로 업데이트
            elif diag == max_diag:
                res = max(res, a * b)
                
        # 가장 긴 대각선을 가진 사각형 중 가장 큰 넓이 반환
        return res

Runtime : 0ms
리스트를 한번만 탐색해 바로바로 최댓값을 구해 갱신하고 저장하여 O(n)의 시간복잡도를 갖는다.
리스트를 추가 정의하거나 정렬하는 단계도 거치지 않아서 훨씬 효율적이고 빠르게 동작한다.

✏️ 회고

문제가 Easy였지만 간단한 문제인 와중에도 훨씬 더 효율적인 다양한 풀이들을 확인할 수 있었다. 문제를 풀 때 결과를 따로 저장하고 그 저장된 것 중에 정답을 골라내는 방식으로 풀었다면 바로바로 갱신하여 효율적으로 동작하도록 만들 수 있을지 고민하는 과정을 거쳐야 겠다.