C++로 막대 길이 배열에서 만들 수 있는 사각형과 정사각형의 개수 구하기

문제 소개

이 문제에서는 N개의 정수로 이루어진 배열이 주어지며, 각 정수는 막대(stick)의 길이를 나타냅니다. 우리의 과제는 이 막대들로 만들 수 있는 사각형과 정사각형의 개수를 출력하는 것입니다.

예시를 통해 문제를 더 자세히 살펴보겠습니다.

• 입력 − array = {5, 5, 7, 7, 1, 4}
• 출력 − 1
• 설명 − 변의 길이가 각각 5, 5, 7, 7인 사각형 하나를 만들 수 있습니다.

해결 접근 방법

사각형이나 정사각형을 만들기 위해서는 같은 길이의 막대가 필요합니다. 사각형에는 두 쌍(길이가 같은 막대 4개 중 2쌍)이 필요하고, 정사각형은 네 변이 모두 같으므로 결국 두 쌍의 막대면 충분합니다. 즉, 핵심은 같은 길이를 가진 막대의 쌍(pair)을 찾는 것입니다.

탐색을 효율적으로 하기 위해 다음 순서로 진행합니다.

1. 배열을 먼저 정렬합니다.
2. 정렬된 배열에서 인접한 두 요소를 비교하여 길이가 같은 쌍을 찾습니다.
3. 찾은 쌍의 총 개수를 2로 나누면 만들 수 있는 사각형 또는 정사각형의 개수가 됩니다.

두 쌍이 있어야 하나의 사각형(또는 정사각형)이 완성되므로, 전체 쌍 개수를 2로 나눈 값이 곧 결과가 됩니다.

구현 예제

위 해결 방법을 C++로 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
int countRecSqr(int sticks[], int n) {
    sort(sticks, sticks + n);
    int pairs = 0;
    for (int i = 0; i < n - 1; i++) {
        if (sticks[i]==sticks[i + 1]) {
            pairs++;
            i++;
        }
    }
    return pairs / 2;
}
int main() {
    int sticks[] = { 2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9 };
    int n = sizeof(sticks) / sizeof(sticks[0]);
    cout<<"만들 수 있는 사각형 또는 정사각형의 총 개수는 ";
    cout<<countRecSqr(sticks, n);
    return 0;
}

실행 결과

만들 수 있는 사각형 또는 정사각형의 총 개수는 3

위 예제에서 길이가 같은 막대의 쌍은 {2, 2}, {4, 4}, {4, 4}, {6, 6}, {7, 7}, {9, 9}로 총 6개입니다. 따라서 6 ÷ 2 = 3개의 사각형 또는 정사각형을 만들 수 있습니다.