사각형의 면적은 두 변의 곱으로 계산됩니다. 모든 사각형은 네 개의 변을 가지며, 마주 보는 두 변의 길이는 서로 같습니다. 면적을 계산하려면 길이와 너비라는 두 변의 값이 필요하며, 원하는 결과는 다음과 같이 구할 수 있습니다.
사각형의 면적 = 길이 × 너비
이 문제에서 주어지는 배열에는 사각형을 이룰 수 있는 변들의 값이 무작위 순서로 들어 있습니다. 우리의 과제는 배열에서 가장 긴 두 쌍의 변(총 네 변)을 찾아 사각형이 가질 수 있는 최대 면적을 구하는 것입니다.
입력 예시 1
Arr[] = { 1,2,1,3,4,4,2,3,5,7 }출력 − 배열에서 네 변을 선택해 만든 최대 면적 − 12
설명 − 주어진 배열을 내림차순으로 정렬하면 다음과 같습니다.
Arr[] = { 7,5,4,4,3,3,2,1,1 }이때 가장 큰 두 쌍의 변(총 네 변)은 { (4,4), (3,3) }입니다. 따라서 가능한 최대 면적은 4 × 3 = 12 제곱 단위입니다.
입력 예시 2
Arr[] = { 8,2,5,3,4,9,8,3,5,7 }출력 − 배열에서 네 변을 선택해 만든 최대 면적 − 40
설명 − 주어진 배열을 내림차순으로 정렬하면 다음과 같습니다.
Arr[] = { 9,8,8,7,5,5,4,3,3,2 }이때 가장 큰 두 쌍의 변(총 네 변)은 { (8,8), (5,5) }입니다. 따라서 가능한 최대 면적은 8 × 5 = 40 제곱 단위입니다.
알고리즘 접근 방식
- 사각형의 변들을 담은 정수 배열을 선언합니다. (Arr[])
- 배열의 크기를 저장할 변수를 생성합니다. (n)
- maxArea(int arr[], int n) 함수는 사각형의 최대 면적을 계산하며, 입력 배열과 그 크기를 인자로 받습니다.
- maxArea() 함수 내부에서는 내림차순으로 정렬된 배열 arr[]를 순회하면서 발견한 가장 큰 두 변을 저장하기 위한 배열 Dim[2]를 선언합니다.
- arr[]가 내림차순으로 정렬되어 있으므로 가장 큰 네 개의 변은 반드시 배열의 앞부분에 위치합니다. 따라서 배열을 순회하며 변의 쌍만 찾으면 됩니다.
- 처음에 Dim[]은 0으로 초기화합니다.
- while 루프는 j<2, 즉 dim[0]과 dim[1]에 아직 값이 채워지지 않았고(i<n) 배열의 끝에 도달하지 않은 동안 계속 실행됩니다.
- 길이가 같은 인접한 두 변의 쌍이 발견되면(if(arr[i]==arr[i+1])) 해당 값을 dim[j]에 저장하고 다음 쌍을 찾기 위해 j를 증가시킵니다.
- 최종적으로 dim[0]과 dim[1]의 곱을 결과로 반환합니다.
- 참고 − sort(arr, n)은 arr를 내림차순으로 정렬하는 함수라고 가정합니다.
예제 코드
#include <iostream>
#include <algorithm>
using namespace std;
// 사각형의 최대 면적을 구하는 함수
int maxArea(int arr[], int n){
int dim[2] = {0};
int i = 0, j = 0;
while(j < 2 && i < n){
if(arr[i] == arr[i+1]){
dim[j++] = arr[i];
}
++i;
}
return dim[0] * dim[1];
}
// 드라이버 함수
int main(){
int arr[] = { 1,8,5,1,8,2,5,3 };
int n = 8;
// 배열을 내림차순으로 정렬
sort(arr, arr + n, greater<int>());
cout << "배열에서 네 변을 선택해 만든 사각형의 최대 면적: " << maxArea(arr, n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
배열에서 네 변을 선택해 만든 사각형의 최대 면적: 40
정리
이 접근 방식의 핵심은 배열을 내림차순으로 정렬한 뒤, 앞부분부터 연속된 두 값이 같은 쌍을 두 개 찾는 것입니다. 정렬에 O(n log n), 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 만약 배열에서 같은 길이의 변 쌍을 두 개 찾지 못하면 dim[0]과 dim[1]이 0으로 남아 있어 결과적으로 0이 반환되므로, 사각형을 만들 수 없는 경우도 자연스럽게 처리됩니다.