Full HD 화면상의 직사각형들이 차지하고 있는 총면적

목차

 

코테 문제 중 하나이고,

구글링 후 완벽하게 내는 건 나도 좀 찝찝하고

 

또 이 회사에선 진짜로 "실력이 있는" 사람을 뽑고 싶지..

나처럼 풀이법을 생각해내지 못했는데도, 잘하는 사람인 척

하는 사람은 원하지 않는다고 생각해서

 

내 풀이대로 내고 틀려야 겠다..

 

 

 

 

1. 문제

 

920x1080 픽셀을 가진 Full HD 화면상에 수직선,수평선으로만 이루어진 직사각형들이 놓여 있습니다. 이 직사각형들은 홀로 떨어져 있거나, 일부 겹치거나, 변 또는 꼭지점이 접하거나, 포함관계에 있을 수 있습니다. 이 직사각형들이 차지하고 있는 총면적을 구하는 프로그램을 작성해서 보내주세요 작성하세요. 프로그래밍 언어는 가장 자신있는 것을 사용하세요.

예로 10x10 픽셀을 가진 화면상에 아래와 같은 직사각형들이 있을 수 있습니다.

 

 

입력
각각의 사각형이 하나의 입력줄이 되며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어집니다. 좌표는 왼쪽 위가 (0,0)이고 오른쪽 아래가 (1920, 1080) 입니다. 첫 두 정수는 사각형의 왼쪽 위 꼭지점의 x, y좌표이고 다음 두 정수는 오른쪽 아래 꼭지점의 x, y좌표입니다.

 

1 0 4 2
8 3 9 4
2 3 5 7
4 6 7 8
3 1 6 5
1 8 4 10
7 2 9 5
8 8 10 9
1 4 2 6

 

 

 

 

2. 풀이법(내 풀이)

 

 

2-1. 처음 풀이

 

사격형의 크기를 구해야 한다. 겹쳐지면 같이 계산하는 형식이다.

 

제일 먼저 생각한 게 다 칠해주고, 전체 탐색하면서 세어 주는 것이다.

 

근데 언듯봐도 시간복잡도가 너무 커 보인다.

HD라서 1920 x 1080고 지금 예제는 n이 9니까 총  (1920 x 1080 x n) = 18,662,400 이 정도야 뭐 괜찮지만,,

 

n이 50만 넘어가도, 1억이다.. 1억 당 1초라고 배웠으니 너무 크긴 하다.

 

 

boolean으로 관리해서 중복을 신경 안쓰게 만들었는데 이렇게 하면 또 마지막에 한번 더 전체 탐색 해줘야 하니까..

 

 

2-2. set 활용

 

그래서 고민 끝에 생각한 게 지금 중요한 건 좌표의 중복을 어떻게 관리하냐? 이다

들어 있는 좌표를 저장해주는데 중복이 있을수도 있음을 set으로 관리해서 저장해주면

그 수만 size로 세면 될 것 같았다.

 

사실 이 코드도 근본적인 해결을 할 수 없다..

전체 탐색을 줄여주고, 미미한 다른 배열로 boolean[][]이 메모리 절약 정도?..

 

사실 내 알고리즘 실력으론 떠올리지 못했다.

 

 

 

 

 

3. 완벽한 풀이법(구글링)

 

3-1. 스위핑(Sweeping) 알고리즘

 

 

 

스위핑 (Sweeping)은 의미처럼 쓸어가는 알고리즘을 뜻함

보통 한 쪽 방향부터 시작해서 다른 방향으로 진행하며 탐색하는 과정을 구현하는 상황을 의미한다.

 

 

주요 특징으로는

 

1. 이벤트 기반 처리: 특정 좌표에서 발생하는 이벤트를 정의하고, 이를 순서대로 처리
2. 정렬: 이벤트를 특정 기준(예: x좌표, y좌표)에 따라 정렬하여 순차적으로 처리
3. 효율성: 전체 좌표를 탐색하지 않고, 관련 있는 좌표만 처리하므로 효율적

 

 

• 중요한 순간만 체크: 직사각형이 시작하거나 끝나는 지점을 기록.
• 한 방향으로 훑기: 예를 들어, 위에서 아래로(y축) 훑으면서 어떤 x좌표가 덮여 있는지 확인.
• 효율적으로 계산: 중복된 부분은 한 번만 세고, 필요한 계산만 함.

 

 

 체크 후 정렬된 좌표를 순차적으로 탐색하기! 이 때 중복된 부분은 계산하지 않게

 

 

이렇게 말해선 이해가 안간다...

그래서 직선으로 된 예제를 보고 왔는데

이해가 쉽다.

 

 

 

3-2 직선의 스위핑

 

 

https://blogshine.tistory.com/120

 

시작지점과 종료시점을 정하고, 그 선의 끝라인을 입력에 따라 바꿔주면 된다.

겹치지 않는 부분이 온다면 다시 그 때부터 시작라인을 잡아주면 됨

 

시작 지점 1에서부터 3으로 하늘색 선,

그 다음 2~5는 겹치는 부분이 있으니 1~5로 끝나는 지점을 바꿔주고

 

이벤트라는 건 쉽게 말해 직사각형이 시작이나 끝 지점만 기록!

 

 

 

 

3-3 이제 평면에서의 스위핑

 

직선을 보고오니 훨씬 이해가 조금은 된다.

저 위 이제 사각형만 사실 그려주면 되는 것이다.

 

처음에는 나도 사각형 속까지 말고 테투리를 활용하는 방법이 어디 없을까 했는데 이걸 여기까지 확장시키진 못했다..

 

살짝 어려운 부분은 평면의 경우에는 직선과 다르게 x부분도 계산해야 한다.

 

y를 기준을 잡자면 어차피 y1을 시작 지점 y2를 끝 지점으로 임의로 잡는다.

 

 

 

각 직사각형마다 세로변 2개씩을 추출한다. 둘 중 하나는 시작하는 세로변(x좌표가 작음), 하나는 끝나는 세로변이다. 이들을 x좌표 순으로 정렬하고 순서대로 훑으면서 ②③을 수행한다.

 

② 바로 전에 훑은 세로변과의 x좌표 차를 dx라 하자. 현재 y좌표 구간들 중 1 이상의 값을 가진 칸의 개수를 센 뒤 dx와 곱해서 결과에 더한다.

③ 이번 세로변이 시작하는 세로변이면, 세로변 안에 속하는 y좌표 구간들에 1을 더한다. 끝나는 세로변이면, 구간들에 1을 뺀다.