[Leetcode]3111. Minimum Rectangles to Cover Points

문제 요약

• 알고리즘 분류: 그리디
• 난이도: Medium
• 문제내용:
  • 2차원 배열 points, points[i] = [xi, yi] 와 정수 w가 주어진다. w는 사각형 가로 길이이다.
  • 사각형의 범위가 (x`, 0) , (x` + w, 0), (x`, y`), (x` + 2, y`)로 이루어 진게 몇개가 있습니다.
  • 각 points 사각형안에 포함이 되어 있습니다. 모든 점이 사각형 안에 포함 될때 최소 몇 개 사형이 필요한지 반환 하세요.
• 사이트 주소: https://leetcode.com/problems/minimum-rectangles-to-cover-points/description/

문제풀이 

 이번 문제는 모든 경우의 수로 구하면 시간초과가 날것이다. 그래서 최적의 시간내로 풀수 있는 그리디로 풀어야 통과가 되는 문제이다. 그리디에 관한 개념은 아래 글에서  확인 해보면 된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근방법

 

그리디 유형 문제는 구현은 어렵지 않지만 많은 생각을 요구합니다. 이번 문제에서는 O(N)의 탐색으로 해결해야 합니다. 이번 문제에서 y축은 무시해도 됩니다. 그 이유는, w가 x의 시작 위치라고 하면 최대 가로 길이가 x + w이고, y에 대한 최대 길이는 언급되지 않았기 때문입니다. 따라서 x축만 고려하면 됩니다.

문제를 해결하는 방법은 다음과 같습니다:

1. 좌표를 x축 기준으로 정렬합니다.
2. point[0]의 x 위치에서 시작하여 x + w 범위 내에 있는지 확인합니다.
3. 범위를 벗어나면 count를 +1 증가시키고, 현재 x좌표부터 다시 x + w까지 탐색합니다.

이 과정을 반복하면 아래 그림처럼 문제를 해결할 수 있습니다.

이렇게 구현하면 시간 복잡도는 O(NlogN)나온다. 그 이유는 points 탐색 하기 이전 points 정렬 하는 단계가 시간 복잡도를 더 많이 소모하기 때문이다.

Code

Python

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        
        points.sort() # 위치 x 축 기준으로 정렬
        count = 1 # 개수
        startLocation = points[0][0] # x축 시작위치 

        for point in points[1:]:
            # 사각형 범위 범어날때
            # 개수 +1, 시작 위치를 x좌표 값으로 지정한다.
            if point[0] > startLocation + w:
                count += 1
                startLocation = point[0]
        return count

Java

class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        
        // points 정렬
        Arrays.sort(points, (o1, o2) -> o1[0] - o2[0]);

        int startLocation = points[0][0]; // x축 왼쪽 위치
        int count = 1; // 사각형 개수
        for (int[] point : points){
            // x축 위치가 사각형 범위에 벗어 날때
            // 개수 +1 증가와 x축 시작 위치를 다시 지정한다.
            if(point[0] > startLocation + w ){
                count++;
                startLocation = point[0];
            }

        }

        return count;
    }
}