[백준/파이썬][Gold IV] 합집합 - 14411

[Gold IV] 합집합 - 14411

문제 링크

성능 요약

메모리: 233848 KB, 시간: 3316 ms

분류

자료 구조, 정렬, 스택

제출 일자

2025년 2월 3일 23:52:37

문제 설명

직교 좌표계에 존재하는 N개의 직사각형이 주어집니다. 주어진 N개의 직사각형은 중심은 모두 직교좌표계 가운데(원점)이며, 직사각형의 네 개의 변은 좌표축과 평행합니다. 각 사각형은 폭 (x 축을 따라)과 높이 (y 축을 따라)로 고유하게 식별됩니다. 아래 그림은 첫 번째 샘플 테스트를 보여줍니다.

디자인학부 학생인 미추홀 군은 각 사각형을 특정 색상으로 채색했으며, 이제는 종이의 채색된 부분의 면적(넓이)을 알고 싶어합니다. 즉, 미추홀 군은 적어도 하나의 직사각형에 속하는 영역(모든 직사각형의 합집합)의 면적을 알고 싶습니다.

입력

첫 번째 입력 줄에는 직사각형 수인 정수 N (1 ≤ N ≤ 1 000 000)이 주어집니다.

다음의 N 행에는 각각 해당 사각형의 크기가 너비(X) 와 높이 (Y)로 주어지며, X와 Y는 모두 짝수인 정수로 (2 ≤ X, Y ≤ 10⁷)범위를 갖습니다.

출력

한줄로 색칠된 사각형의 합집합 영역의 넓이를 출력합니다.

풀이

def main() :
    N = int(input())
    squares = [list(map(int, input().split())) for _ in range(N)]

    squares.sort(reverse=True)  # x를 기준으로 내림차순 정렬

    res = 0         # 최종 넓이
    prev_y = 0      # 직전 y

    for x, y in squares :
        if y > prev_y : # 현재 y 가 전 y 보다 클 경우
            res += x * (y - prev_y)
            prev_y = y
    print(res)

    
main()

왜 이걸 바로 풀지 못했을까 생각이 든다.

1. x를 기준으로 내림차순 정렬을 진행
2. y를 기준으로 큰지 작은지를 비교
   1. y가 prev_y 보다 크면 : 위에 삐져나와있는 부분만 결과값에 더한다.
   2. prev_y 가 더 크면 : 완전히 가려진다는 의미로 넓이를 포함시키지 않는다.

이 단계를 보고 나서야 이해가 되었다. 생각보다 간단했는데, 이 생각을 해내는 거에서 어려움을 겪었다.

먼저 x 를 내림차순으로 정렬하면서 이 뒤에 x 값은 생각하지 않기로 한다. 

만약 x, y 둘 다 작을 경우, 굳이 결과값에 더할 필요가 없기 때문에 생략.

y가 클 경우, 위에 삐져나와있는 부분만 더해주면 되기 때문에 위와 같은 식이 나오게 된다.