Skip to main content

3025 - Find the Number of Ways to Place People I

info

풀이 키워드​

스포주의

정렬 수학


풀이 코드​

info
  • 메모리: 44520 KB
  • 시간: 7 ms
class Solution {
    int[][] points;

    boolean check(int A, int B) {
        // check if others are in the A-B area
        int sx = points[A][0];
        int ex = points[B][0];
        int sy = points[B][1];
        int ey = points[A][1]; 
        for (int K = A+1; K < B; ++K) {
            int x = points[K][0];
            int y = points[K][1];
            if (sx <= x && x <= ex && sy <= y && y <= ey) return false;
        }

        return true;
    }

    public int numberOfPairs(int[][] points) {
        this.points = points;
        Arrays.sort(points, (a, b) -> {
            // x ASC(➡️) y DESC(⬇️)
            int ax = a[0];
            int ay = a[1];
            int bx = b[0];
            int by = b[1];
            if (ax != bx) return ax - bx;
            else return by - ay; 
        });

        int ans = 0;
        for (int A = 0; A < points.length-1; ++A) {
            for (int B = A+1; B < points.length; ++B) {
                if (points[A][1] < points[B][1]) continue; // A is not upper left
                if (check(A, B)) ++ans; 
            }
        }

        return ans;
    }
}

풀이 해설​

2차원 평면의 [x, y]가 주어질 때, 점 2개를 선택해서 사각형을 형성하되 다음의 조건을 지켜야 한다.

  • 반드시 왼쪽 위 점과 오른쪽 아래의 점을 통해 사각형을 만들어야 함.
  • 형성된 사각형 내부에 다른 점이 있으면 안됨 (경계선도 내부에 포함)

그리고 예시를 보면 동일 축에 위치해도 사각형으로 인정된다.

여기서 왼쪽 위 점을 A, 오른쪽 아래의 점을 B라고 하자.

Arrays.sort(points, (a, b) -> {
    // x ASC(➡️) y DESC(⬇️)
    int ax = a[0];
    int ay = a[1];
    int bx = b[0];
    int by = b[1];
    if (ax != bx) return ax - bx;
    else return by - ay; 
});

우선 A부터 선택해야 하므로 x좌표 기준 오름차순, y좌표 기준 내림차순으로 정렬한다.
(문제에서 A is on the upper left side of B 라는 식으로 약간 헷갈리게 만드는데 기준을 A부터 잡는게 발상하기 편함)

int ans = 0;
for (int A = 0; A < points.length-1; ++A) {
    for (int B = A+1; B < points.length; ++B) {
        if (points[A][1] < points[B][1]) continue; // A is not upper left
        if (check(A, B)) ++ans; 
    }
}

그리고 순차적으로 A, B 포인트를 잡아서 다음의 2가지를 검사한다.

  1. A가 B의 upper left에 있는지?
  2. check: 사각형 A-B 영역 상에 다른 점(K)이 있지 않은지?

1번을 검사하는 이유는 정렬 로직 상 하단의 그림처럼 A가 B의 lower left에 위치하게 될 수도 있기 때문이다.

이처럼 x축 우선 정렬이라 A가 left-side인건 보장하지만 y축으로 upper-side 인지는 보장하지 못한다.


메모​

  • 정렬 발상 및 custom comparator 연습하기 좋은 문제
  • A가 Alice이고 B가 Bob인거 첨 알음