699. Falling Squares

[zeikar]

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