C++로 각 플레이어의 카드 합계를 동일하게 만드는 분배 방법 구현하기

문제 개요

길이가 n인 배열 A가 있다고 가정해 보겠습니다. 이때 n은 짝수이며, A[i]는 i번째 카드에 적힌 숫자를 의미합니다. 게임에 참여할 플레이어는 총 n/2명이고, 게임 시작 시 각 플레이어는 두 장의 카드를 가져갑니다. 우리가 찾아야 하는 것은 모든 플레이어가 받은 두 카드에 적힌 숫자의 합이 서로 같아지도록 카드를 분배하는 방법입니다.

예를 들어 입력이 A = [1, 5, 7, 4, 4, 3]이라면 출력은 [(0, 2), (5, 1), (3, 4)]가 됩니다. 그 이유는 A[0] + A[2] = 8, A[5] + A[1] = 8, A[3] + A[4] = 8로, 세 플레이어 모두 카드 합이 8로 동일하기 때문입니다.

해결 접근 방식

이 문제는 정렬을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 각 카드의 값과 원래 인덱스를 하나의 쌍(pair)으로 묶어 저장한 뒤, 카드 값을 기준으로 오름차순 정렬합니다. 그다음 가장 작은 값과 가장 큰 값을 차례대로 짝지어 줍니다. 즉, i번째로 작은 카드와 i번째로 큰 카드를 한 쌍으로 묶어 각 플레이어에게 나눠주는 방식입니다. 이렇게 하면 값과 함께 저장해 둔 인덱스를 통해 어떤 카드들이 짝이 되었는지 그대로 출력할 수 있습니다.

알고리즘 단계

n := 배열 A의 크기
크기가 n인 pair 배열 p 선언
i := 0부터 i < n까지 1씩 증가시키며 반복:
    p[i].first := A[i]
    p[i].second := i
배열 p를 오름차순으로 정렬
i := 0부터 i < n / 2까지 1씩 증가시키며 반복:
    p[i].second와 p[n - i - 1].second 출력

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A){
    int n = A.size();
    pair<int, int> p[n];
    for (int i = 0; i < n; i++){
       p[i].first = A[i];
       p[i].second = i;
    }
    sort(p, p + n);
    for (int i = 0; i < n / 2; i++)
       cout << "(" << p[i].second << ", " << p[n - i - 1].second <<"), ";
   }
   int main(){
       vector<int> A = { 1, 5, 7, 4, 4, 3 };
       solve(A);
   }

입력

{ 1, 5, 7, 4, 4, 3 }

출력

(0, 2), (5, 1), (3, 4),

복잡도 분석

카드 값과 인덱스를 저장하는 과정은 O(n)의 시간이 걸리고, 정렬 과정에서 O(n log n)의 시간이 소요됩니다. 따라서 이 알고리즘의 전체 시간 복잡도는 O(n log n)입니다.