프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #25

이번 편은 TIP이 생각나서 써봅니다.

 

2차원 평면에 사각형을 여러개를 그렸을 때 (중첩될 수 도 있음)

(입력 데이터로 사각형의 양 대각선 좌표를 주어짐)

 

1. 사각형이 표시하는 면적은 얼마인가?

2. 사각형이 1번만 겹치는 부분의 면적은 얼마인가?

3. 사각형이 겹치지지 않는 부분의 면적은 얼마인가?

 

이런 종류의 문제를 푸는 방법으로 플레인 스위핑이라는 유명한 방법이 있습니다.

http://blog.naver.com/PostView.nhn?blogId=choyi0521&logNo=220020192420

 

하지만 유명한 방법을 모두 알 수 없기도 하고

사각형이 표시하는 면적이 적고 사각형의 갯수가 적다면 아주 쉽게 푸는 방법이 있습니다.

 

최대 범위만큼 메모리를 잡고 각 사각형 마다 안에 면적안에 1을 추가합니다.

그럼 겹쳐지지 않는 부분은 1만 써있게 되고

2번 겹쳐지는 부분은 2, 3번 겹쳐지는 부분은 3이 됩니다.

 

위의 1번 문제는 모든 숫자의 갯수를 세면 되고

2번 문제는 2의 갯수를 세면 되고

3번 문제는 1의 갯수만 세면 됩니다.

 

간단한 것인데 쉽게 생각나면 쉽게 풀고 아니면 어렵게 풀어야 하는 문제입니다.

 

하지만 사각형이 무지 크면 사각형에 1을 써넣는 작업이 너무 많아서 TimeOut이 되는

방법입니다. 초급/입문으로만 쓰세요.

 

#삼성_소프트웨어_역량_테스트