만들 수 없는 가장 작은 동전 합

문제

주어진 동전들 중 어떤 부분집합도 선택할 수 있습니다. 동전의 값이 같더라도 각 동전은 최대 한 번씩만 사용할 수 있습니다. 어떤 선택으로도 만들 수 없는 가장 작은 양의 정수 금액을 구하세요.

missing_coin_sum(coins) 함수를 구현하세요.

coins: 사용 가능한 동전들의 값입니다. 중복된 값은 서로 다른 동전을 의미합니다.

만들 수 없는 가장 작은 양의 정수 금액을 반환하세요.

1 ≤ 동전의 개수 ≤ 200,000. 각 동전의 값은 1 이상 1,000,000,000 이하입니다.

예시 1

입력:
coins = [1, 1, 4]

예상 출력:
expected = 3

입력:
std::vector<long long> coins = {1, 1, 4};

예상 출력:
long long expected = 3;

입력:
long[] coins = new long[] {1, 1, 4};

예상 출력:
long expected = 3;

1과 2는 값이 1인 동전들로 만들 수 있습니다. 3을 만들 수 있는 부분집합은 없습니다.

예시 2

입력:
coins = [2, 3]

예상 출력:
expected = 1

입력:
std::vector<long long> coins = {2, 3};

예상 출력:
long long expected = 1;

입력:
long[] coins = new long[] {2, 3};

예상 출력:
long expected = 1;

모든 동전의 값이 최소 2이므로 1을 만들 방법이 없습니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

동전을 정렬한 뒤, 가장 작은 값부터 만들 수 있는 최소 합을 늘려 간다.

힌트 2

다음 동전이 첫 번째로 만들 수 없는 합보다 크면, 그 값은 절대 만들 수 없다.

힌트 3

중복은 현재 도달 가능한 범위를 끊김 없이 넓힐 때만 도움이 된다.

예상 복잡도

O(n log n) time, O(1) extra space, excluding sorting implementation details

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.