[LeetCode] 1798. Maximum Number of Consecutive Values You Can Make

문제 출처: https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/

Maximum Number of Consecutive Values You Can Make - LeetCode

 

문제

소유하고 있는 n개의 동전을 표현한 길이 n의 배열 coins가 주어진다. coins[i]는 ith 동전의 값이다. n개의 코인 중에서 일부를 선택하여, 그들의 합인 x를 만들 수 있다.

 

0부터 시작하여 주어진 coins를 이용해서 만들 수 있는 연속적인 정수의 수 중 가장 큰 값을 반환하라.

 

동일한 동전을 여러 개 가질 수 있음에 주의하라.

 

예제

Input: coins = [1,3]
Output: 2

Explanation: You can make the following values:
- 0: take []
- 1: take [1]
You can make 2 consecutive integer values starting from 0.

Input: coins = [1,1,1,4]
Output: 8

Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.

 

풀이

[0, x] 까지의 숫자를 만들 수 있다고 할 때, 임의의 값 v가 새로 주어지면 만들 수 있는 수의 범위에 대해 생각해보자.

 

v와 x+1과의 관계를 살펴보면 아래 3가지 경우로 나누어진다. x가 아닌 x+1과 비교하는 이유는 연속된 수를 만들기 위해서 [0, x]에서 필요한 수는 x+1이기 때문이다.

• v < (x + 1)
• v == (x + 1)
• v > (x + 1)

 

첫 번째 케이스인 v < (x+1) 을 보면, v에 현재까지 가능한 값을 더하는 것으로 [0, v+x]까지 확장이 가능하다.두 번째 케이스인 v == (x+1)을 보면, v 자체가 x+1이기 때문에 최소한 [0, x+1]까지 확장이 가능하며 나아가 [0, v+x]까지 확장될 수 있다.

세 번째 케이스인 v > (x+1)을 보면, v가 x+1보다 크기 때문에, 현재 범위에서 x+1을 만들 방도가 존재하지 않는다. 그렇기 때문에 문제의 0을 포함하는 연속된 수 조건을 깨뜨리는 상황이 만들어진다.

 

이제 처음부터 가정했던 [0, x]에 대해서 생각해보자.

 

최초 [0, 0]에서 시작하여 coins 값에 따라 점차 확장시켜 가는 방법을 생각할 수 있다. 이때 coins의 순서에 대해서 주의해야 한다.

coins = [1, 1, 3]
[0, 0] => [0, 1] => [0, 2] => [0, 5]

coins = [1, 3, 1]
[0, 0] => [0, 1] => X

위의 예는 동일한 원소지만 순서가 다른 coins에서 어떤 결과가 나오는지를 보여준다. [0, 0]에서 점진적으로 확장하기 위해서는 coins가 오름차순으로 정렬되어 있어야 한다는 것을 유추해볼 수 있다.

 

지금까지의 내용을 코드로 작성하면 다음과 같다.

var foo = function(coins) {
    coins = coins.sort((a,b) => a - b);

    let left = 0, right =0;
    for (let i = 0; i < coins.length; i++) {
        if (right+1 < coins[i]) { break; }
    }
    return right+1;
}

 

Github: 1798.js

opwe37/Algorithm-Study