rect라는 배열이 주어졌다고 가정해 봅시다. rect[i]는 두 개의 원소 [len_i, wid_i]를 가지며, 각각 i번째 직사각형의 가로 길이와 세로 길이를 나타냅니다. 이때 k <= len_i 그리고 k <= wid_i가 모두 성립한다면, i번째 직사각형을 잘라 한 변의 길이가 k인 정사각형을 만들 수 있습니다.
예를 들어 직사각형 [4, 6]이 있다면, 이것을 잘라서 만들 수 있는 정사각형의 한 변 길이는 최대 4입니다. 여기서 maxLen은 주어진 직사각형들 중 어느 하나에서 얻을 수 있는 가장 큰 정사각형의 한 변 길이를 의미합니다. 우리가 구해야 할 것은, 한 변의 길이가 maxLen인 정사각형을 만들 수 있는 직사각형의 개수입니다.
예를 들어 입력이 rect = [[6,9],[4,10],[6,13],[17,6]]이라면 출력은 3이 됩니다. 각 직사각형에서 만들 수 있는 가장 큰 정사각형의 한 변 길이는 [6, 4, 6, 6]이고, 최댓값인 6에 해당하는 직사각형이 세 개이기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
m := 새로운 리스트 생성
rect의 각 r에 대해 다음을 반복합니다.
r의 최솟값(즉, 해당 직사각형에서 만들 수 있는 최대 정사각형의 한 변 길이)을 m의 끝에 추가
m에서 최댓값이 등장하는 횟수를 세어 반환
예제 코드 (Python)
아래 구현을 통해 더 잘 이해해 봅시다.
def solve(rect): m = [] for r in rect: m.append(min(r)) return m.count(max(m)) rect = [[6,9],[4,10],[6,13],[17,6]] print(solve(rect))
입력
[[6,9],[4,10],[6,13],[17,6]]
출력
3
이 알고리즘의 시간 복잡도는 O(n)으로, 각 직사각형의 짧은 변만 확인하면 되므로 매우 효율적입니다. 직사각형을 자르는 문제는 결국 "짧은 변"이 곧 만들 수 있는 최대 정사각형의 한 변이라는 핵심 아이디어만 기억하면 손쉽게 풀 수 있습니다.