길이와 너비로 표현된 직사각형 목록이 있다고 가정해 보겠습니다. 각 직사각형은 90도 회전할 수 있으며, 회전하면 길이와 너비가 서로 바뀌게 됩니다. 이때 모든 직사각형을 너비를 기준으로 비증가 순서(non-increasing order), 즉 같은 값은 허용하되 감소하지 않는 내림차순으로 나열할 수 있는지 확인해야 합니다.
예를 들어 입력이 rects = [[4, 5], [5, 7], [4, 6]]라고 해보겠습니다. 현재 너비는 [5, 7, 6]입니다. 마지막 두 직사각형을 회전하면 너비가 [5, 5, 4]가 되어 비증가 순서를 만족하므로 결과는 True가 됩니다.
접근 방법
이 문제는 그리디(greedy) 전략으로 해결할 수 있습니다. 왼쪽에서 오른쪽으로 직사각형을 하나씩 살펴보면서, 이전 단계에서 정한 너비 제한(m)을 넘지 않는 선에서 가능한 한 큰 값을 현재 너비로 선택하는 것입니다. 이렇게 하면 뒤에 오는 직사각형에게 최대한 여유를 남겨두게 됩니다.
구체적인 단계는 다음과 같습니다.
- m을 충분히 큰 값(99999)으로 초기화합니다.
- 0부터 직사각형 개수까지 반복합니다.
- i번째 직사각형의 길이와 너비 중 최댓값이 m 이하라면, m을 그 최댓값으로 갱신합니다(회전 없이 사용).
- 그렇지 않고 최솟값이 m 이하라면, m을 그 최솟값으로 갱신합니다(90도 회전하여 사용).
- 둘 다 m보다 크다면 어떻게 배치해도 조건을 만족할 수 없으므로 False를 반환합니다.
- 모든 직사각형을 통과하면 True를 반환합니다.
예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(rect):
m = 99999
for i in range(len(rect)):
if max(rect[i][0], rect[i][1]) <= m:
m = max(rect[i][0], rect[i][1])
elif min(rect[i][0], rect[i][1]) <= m:
m = min(rect[i][0], rect[i][1])
else:
return False
return True
rects = [[4, 5], [5, 7], [4, 6]]
print(solve(rects))입력
[[4, 5], [5, 7], [4, 6]]
출력
True
복잡도 분석
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간을 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 따라서 직사각형 개수가 많아져도 효율적으로 동작합니다.