Leetcode 2345. Finding the Number of Visible Mountains

문제

You are given a 0-indexed 2D integer array peaks where peaks[i] = [xi, yi] states that mountain i has a peak at coordinates (xi, yi). A mountain can be described as a right-angled isosceles triangle, with its base along the x-axis and a right angle at its peak. More formally, the gradients of ascending and descending the mountain are 1 and -1 respectively.

A mountain is considered visible if its peak does not lie within another mountain (including the border of other mountains).

Return the number of visible mountains.

• 0으로 시작하는 인덱스를 가진 2차원 정수 배열 peaks가 주어지는데 여기서 peaks[i]는 i번째 산의 꼭대기 좌표인 (xi, yi)를 나타냅니다.
• 모든 산은 x축 위에 밑변이 있고 꼭대기가 90도인 직각 이등변 삼각형 모양이며, 이는 곧 산을 올라가는 빗변의 기울기는 1이고 내려가는 빗변의 기울기는 -1이라는 뜻입니다.
• 이때 어떤 산의 꼭대기가 다른 산의 내부나 테두리에 포함되지 않는 경우에만 해당 산이 보인다고 판단하며, 결과적으로 이렇게 보이는 산이 총 몇 개인지 구해야 합니다.

예시

• 가려지지 않는 산은 총 2개

제한

• $1 <= peaks.length <= 10^5$
• $peaks[i].length == 2$
• $1 <= x_i, y_i <= 10^5$

풀이

• 일단 먼저 산이라는 개념을 평탄화 해서 2D로 둘 필요가 있다.
• 해당 산이 차지하는 x축 좌표만 보면 해당 x축 좌표는 [x-y, x+y]임을 알수 있다.
• 이것을 비교해 봤을때 한 산의 두 좌표가 다른 산 내부에 포함되면 이 산은 가려진다는것을 알수 있다.
• 그렇기에, 좌표점을 해당 두 x좌표로 변환 한 뒤에

1. 시작점에 대해 오름차순 정렬, 끝점에 대해 내림차순 정렬한다.
   • 그렇게 된다면, 특정 시작점에 대해 가장 큰, 절대 가려지지 않는 산 하나를 확인할수 있다.
2. 끝점을 계속 파악하면서 가려지는 산은 빼고 가려지지 않는 산만 골라서 갯수를 구한다.

class Solution:
    def visibleMountains(self, peaks: List[List[int]]) -> int:
        mountains = [(x - y, x + y) for x, y in peaks]

        cntr = Counter(mountains)

        # start를 오름차순으로 정렬하고 그 이후 end를 내림차순으로 정렬한다. ( start가 같은것중 end가 멀리있는것 순서 )
        mountains.sort(key=lambda k: (k[0], -k[1]))

        ans = 0

        # 산에 의해 가려지는 마지막 부분 저장
        final = -float('inf')

        for start, end in mountains:
            # 산이 가려지는지 확인하고, 가려지면 넘긴다.
            if final >= end:
                continue

            # 가려지지 않는 산이라고 해도 똑같은 산이 2개 있으면 서로 가리기 때문에 안된다.
            if cntr[(start, end)] == 1:
                ans += 1

            final = end

        return ans