Problem link
https://leetcode.com/problems/falling-squares/
Problem Summary
위에서 블록이 차례대로 떨어질 때 현재 가장 높은 블록을 순서대로 출력하는 문제.
Solution
인풋 크기가 작으므로 n^2 풀이로 풀린다!
heights 맵을 만들어 해당 구간의 높이를 저장해두면서 다른 블록이 떨어질 때 겹치는 구간이 있는지 보고 있다면 그만큼 높이를 더해서 추가하는 방식으로 동작한다.
참고로 세그먼트 트리나 이분 탐색 등으로 nlogn 풀이도 가능하다.
https://leetcode.com/problems/falling-squares/discuss/108764/Easy-and-Concise-Python-Solution-(97) 참고.
Source Code
from typing import List
class Solution:
def fallingSquares(self, positions: List[List[int]]) -> List[int]:
results = []
heights = {}
max_height = 0
for left, side_length in positions:
start = left
end = left + side_length - 1
nearby = [key for key in heights.keys() if (start <= key[1] and key[0] <= end)]
if len(nearby) > 0:
h = max(heights[key] for key in nearby) + side_length
else:
h = side_length
heights[(start, end)] = h
max_height = max(max_height, h)
results.append(max_height)
return results