카드를 버린 후 남은 카드 숫자의 최소 합계를 구하는 C++ 코드

배열 T에 다섯 개의 숫자가 저장되어 있다고 가정해 봅시다. 다섯 장의 카드가 있으며, 각 카드에는 하나의 숫자가 적혀 있습니다. i번째 카드에는 T[i]라는 숫자가 적혀 있는 형태입니다.

우리는 일부 카드를 버릴 수 있으며, 목표는 남아 있는 카드에 적힌 숫자의 합을 최소화하는 것입니다. 단, 같은 숫자가 적힌 카드 두 장 또는 세 장을 버리는 행위는 최대 한 번만 허용됩니다. 만약 같은 숫자를 가진 카드 두 장 또는 세 장을 선택하는 것이 불가능하다면, 어떤 카드도 버리지 않습니다. 이 조건에서 만들 수 있는 최소 합계를 구해야 합니다.

예를 들어 입력이 T = [7, 3, 7, 3, 20]이라면 출력은 26이 됩니다. 숫자 7이 적힌 카드 두 장을 버리면 남은 카드의 합은 3 + 3 + 20 = 26이 되기 때문입니다.

문제 해결 접근 방식

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

먼저 전체 카드 숫자의 총합(m)을 계산하고, 각 숫자의 등장 횟수를 크기 101의 배열(k)에 기록합니다.
그다음 각 숫자를 확인하면서 해당 숫자가 두 번 이상 나타난 경우, 그 숫자로 이루어진 카드 두 장 또는 세 장(가능한 만큼)을 버렸을 때의 합을 계산합니다.
버린 숫자 × 버린 장수만큼 총합에서 차감한 값들 중 가장 작은 값이 정답이 됩니다.

n := 5
m := 0
크기가 101인 배열 k를 선언하고 0으로 초기화
for initialize i := 0, when i < n, update (increase i by 1), do:
    a := T[i]
    m := m + a
    (increase k[a] by 1)
M := m
for initialize i := 0, when i < 101, update (increase i by 1), do:
    if k[i] > 1, then:
        M := minimum of M and (m - i * (minimum of 3 and k[i]))
return M

C++ 구현 예제

아래 구현 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> T)
{
    int n = 5, m = 0, a;
    int k[101] = { 0 };
    for (int i = 0; i < n; i++)
    {
        int a = T[i];
        m += a;
        k[a]++;
    }
    int M = m;
    for (int i = 0; i < 101; i++)
        if (k[i] > 1)
        {
            M = min(M, m - i * (min(3, k[i])));
        }
    return M;
}
int main()
{
    vector<int> T = { 7, 3, 7, 3, 20 };
    cout << solve(T) << endl;
}

입력

{ 7, 3, 7, 3, 20 }

출력

이 알고리즘의 시간 복잡도는 O(n + K)입니다. 여기서 n은 카드의 개수(5), K는 카드에 적힐 수 있는 최대 숫자 범위(101)입니다. 카드 개수가 고정되어 있어 사실상 상수 시간에 동작하며 매우 효율적입니다.