C++로 프로그래머 학생 그룹을 나누는 최소 팀 수 구하기

n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. A[i]는 i번째 학생의 프로그래밍 실력을 나타내며, 배열의 모든 요소는 서로 다릅니다. 우리는 이 학생들을 다음 조건에 맞게 팀으로 나누려고 합니다.

|A[i] - A[j]| = 1인 두 학생 i와 j가 같은 팀에 속하지 않도록 합니다.
팀의 수는 가능한 한 최소여야 합니다.

예를 들어 입력이 A = [2, 3, 4, 99, 100]이라면 출력은 2가 됩니다. 그룹이 [2, 3, 4]와 [99, 100]으로 나뉘기 때문입니다.

풀이 접근 방식

이 문제를 해결하기 위해 다음 단계를 따릅니다.

핵심 아이디어는 간단합니다. 배열을 오름차순으로 정렬한 뒤, 인접한 두 요소의 차이가 정확히 1인 경우가 하나라도 존재하면 최소 2개의 팀이 필요합니다. 그렇지 않다면 실력 차이가 1인 학생 쌍이 없으므로 모든 학생을 한 팀으로 묶을 수 있습니다.

dem := 1
배열 A를 정렬합니다
i := 1부터 A의 크기보다 작을 때까지 반복합니다:
    만약 A[i] - A[i - 1]이 1과 같다면:
        dem := 2
dem을 반환합니다

예제 코드

아래의 C++ 구현을 살펴보면 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int dem = 1;
    sort(A.begin(), A.end());
    for (int i = 1; i < A.size(); i++)
        if (A[i] - A[i - 1] == 1)
            dem = 2;
    return dem;
}
int main() {
    vector<int> A = { 2, 3, 4, 99, 100 };
    cout << solve(A) << endl;
}

입력

{ 2, 3, 4, 99, 100 }