AlgoSpot Quiz '사각형 그리기 (DRAWRECT)' 문제 풀이.
▶ DRAWRECT 문제 분석
- input : 입력의 첫 행은 T 값이며, 테스트 케이스(test case)의 갯수이다.
나머지 입력은 x, y 좌표 값을 공백으로 구분한 행들이며, 3 * T 갯수 만큼 입력된다.
- processing : T 만큼 반복하면서, 3개의 2차원 좌표를 이용해 마지막 좌표를 계산한다.
- output : 계산된 마지막 좌표를 출력한다.
입력 값의 범위와 유형은 아래와 같이 표현할 수 있습니다.
▶ 문제 분할
문제 자체가 복잡하지 않기 때문에 세밀한 문제 분할은 필요가 없습니다.
▶ 핵심 논리 구성
4개의 점 중에서 하나가 누락될 경우, 3개의 점으로 구성할 수 있는 경우의 수를 구해 봅니다. 수학의 '조합(combination)'을 활용하면 되겠습니다. 조합(Combination)이란, 서로 다른 개 중 순서를 무시하고 개를 택하는 것이며, 기호로 나타냅니다.
조합을 이용해 4개의 점 중에서 3개의 점을 순서를 구분하지 않고 선택하는 경우의 수를 계산하면, 아래와 같습니다.
4개의 경우의 수를 표 형태로 표현해 보면 다음과 같습니다.
조합 |
Case #1 |
Case #2 | Case #3 | Case #4 |
좌표 |
p1 (x1, y1) p2 (x2, y1) p3 (x1, y2) |
p1 (x1, y1) p2 (x2, y1) p4 (x2, y2) | p1 (x1, y1) p3 (x1, y2) p4 (x2, y2) | p2 (x2, y1) p3 (x1, y2) p4 (x2, y2) |
비고 |
p4 제외 |
p3 제외 | p2 제외 | p1 제외 |
위 표를 통해 얻을 수 있는 핵심 논리는 아래와 같습니다.
직사각형의 3개의 점(point)가 입력되었을 때, x와 y 좌표는 항상 2개는 같고 나머지 하나는 다르다.
다른 값을 가지는 2개의 x, y 좌표 값을 결합하면 4번째 좌표를 얻을 수 있다.
▶ 플랫폼 문제 해결
본 문제는 플랫폼 문제를 해결할 필요가 없습니다.
▶ 핵심 정리
알고리즘 문제 해결을 위해 가장 좋은 도구는 '수학'입니다. 또한, 문제를 풀기 위해서 좌표계 등의 시각적인 도구를 활용하면, 직관적으로 문제를 이해하는데 있어 큰 도움이 됩니다.