C++로 n개의 공을 k명의 학생에게 중복 없이 나눠주는 방법

이 튜토리얼에서는 n개의 공을 k명의 학생에게 나눠주되, 누구도 같은 색의 공을 두 개 이상 받지 않도록 배분하는 방법을 알아보겠습니다.

문제 개요

문제의 아이디어는 간단합니다. 서로 다른 색상으로 이루어진 n개의 공이 있고, 이것을 학생들에게 나눠주어야 합니다. 단, 한 학생에게 같은 색의 공을 두 개 이상 줄 수는 없습니다.

만약 어떤 색상의 공 개수가 학생 수(k)보다 많다면, 그 색의 공을 모두 나누더라도 반드시 누군가 같은 색의 공을 여러 개 받게 됩니다. 이 경우에는 배분이 불가능하므로 "No"를 출력해야 합니다.

예제 입력

n = 10
k = 5
ballsColors = "rrrgbrbgbr"

예제 출력

Yes

위 예제에서 각 색상('r', 'g', 'b')의 개수를 세어 보면, 어떤 색도 학생 수인 5를 초과하지 않습니다. 따라서 모든 학생이 같은 색의 공을 중복해서 받지 않으면서 배분하는 것이 가능합니다.

해결 접근 방식

문제를 해결하는 단계는 다음과 같습니다.

n(공의 개수), k(학생 수), 그리고 각 공의 색상 정보를 초기화합니다.
각 색상별 공의 개수를 저장하기 위해 맵(map)을 초기화합니다.
공의 색상을 하나씩 순회하면서 각 색상별 개수를 셉니다.
색상별 개수를 확인합니다.
- 어떤 색상의 공 개수가 학생 수(k)보다 크다면 배분이 불가능하므로 false를 반환합니다.
- 그렇지 않다면 배분이 가능합니다.
최종 결과를 출력합니다.

C++ 구현 코드

위 로직을 C++ 코드로 구현하면 다음과 같습니다.

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

bool canDistributeBalls(string ballsColors, int n, int k) {
    map<char, int> charCount;
    // 각 색상별 공의 개수를 카운트
    for (int i = 0; i < n; i++) {
        charCount[ballsColors[i]]++;
    }
    // 어떤 색상이라도 학생 수보다 많으면 배분 불가
    map<char, int>::iterator itr;
    for (itr = charCount.begin(); itr != charCount.end(); itr++) {
        if (itr->second > k) {
            return false;
        }
    }
    return true;
}

int main() {
    int n = 10, k = 5;
    string ballsColors = "rrrgbrbgbr";
    if (canDistributeBalls(ballsColors, n, k)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Yes

동작 원리 설명

이 코드의 시간 복잡도는 O(n log n)입니다. 공의 개수만큼 순회하며 카운트하고(O(n)), 맵은 내부적으로 균형 이진 탐색 트리를 사용하므로 삽입과 조회에 O(log n)이 걸리기 때문입니다. 만약 unordered_map을 사용하면 평균 O(n)으로 최적화할 수 있습니다.

핵심 원리는 단순합니다. 같은 색의 공이 k개 이하라면, 각 색의 공을 서로 다른 학생에게 하나씩 나눠줄 수 있기 때문에 반드시 배분이 가능합니다. 반대로 어떤 색이라도 k개를 초과하면 비둘기집 원리(Pigeonhole Principle)에 의해 반드시 누군가 같은 색의 공을 두 개 이상 받게 됩니다.

마무리

이번 튜토리얼에서는 해시 맵(맵 자료구조)을 활용해 색상별 빈도를 계산하고, 조건을 검사하여 공 배분 가능 여부를 판단하는 방법을 배웠습니다. 궁금한 점이 있다면 댓글로 남겨주세요!