[LeetCode] 441. Arranging Coins

문제 출처: https://leetcode.com/problems/arranging-coins/

Arranging Coins - LeetCode

---

문제

n개의 코인을 계단 형태로 쌓으려고 한다. 계단은 i번째 줄에는 정확히 i개의 코인이 있는 형태로 k 줄로 구성합니다. 마지막 줄의 경우 불완전한 형태일 수도 있습니다.

 

n이 주어지면, 계단으로 쌓을 때 완전한 줄의 수를 반환하라.

예제

Input: n = 5
Output: 2

Explanation: Because the 3rd row is incomplete, we return 2.

Input: n = 8
Output: 3

Explanation: Because the 4th row is incomplete, we return 3.

---

풀이

임의의 k에 대해서 k 줄 계단을 만드는데, k 줄 모두 완전한 형태로 만들기 위해서 필요한 코인 수를 계산해보자. 규칙이 존재하는지 살펴보기 위해서 k를 점진적으로 증가시키면서 살펴보았습니다.

k	필요한 코인 수
1	1
2	1+2
3	1+2+3
4	1+2+3+4

위 표를 토대로 생각해보면, k 줄의 계단을 완전하게 쌓기 위해서는 $\Sigma_{i=1}^{k}{i} = \frac{k(k+1)}{2}$개의 코인이 필요함을 알 수 있습니다.

 

이 사실만으로도 단순하게 답을 반환하는 알고리즘을 작성할 수 있습니다.

var arrangeCoins = function(n) {
    let k = 0;
    
    while (sigmaN(k) <= n) { k += 1; }
    k -= 1;
    
    return k;
}

function sigmaN(n) {
	return n*(n+1)/2
}

k를 점진적으로 키우면서 k줄을 완벽하게 채우기 위해 필요한 코인과 주어진 코인을 비교합니다. k 줄을 채우는데 필요한 코인 수보다 주어진 n이 작아지는 순간을 찾는 것입니다. 완벽하게 채울 수 있는 줄이 어디까지인지를 반환하는 것이 문제의 목표이기 때문에 구해진 k보다 1 작은 값을 반환하는 것으로 문제의 해답을 구할 수 있습니다.

 

현재 방식(코드)에서의 문제점을 생각해보자면, n이 커짐과 동시에 답을 찾아내는 시간 또한 선형적으로 늘어날 것입니다. 시간 복잡도로 이야기한다면 현재 코드는 O(n)이라 할 수 있습니다.

 

O(n)이 어때서? 라고 생각할 수도 있지만, 언제나 현재보다 더 나은 방법을 고민하는 일은 중요하다고 생각합니다.

 

가만히 문제를 들여다보면, 만약 정답의 범위를 특정할 수 있다면, 범위 내 한 지점을 선택하고 그 결과에 따라 선택한 지점의 좌측 또는 우측 값의 결과를 유추할 수 있을 것 같습니다.

 

예를 들어, 정답의 범위가 1~6이라 한다면 다음과 같은 방식으로 범위를 줄여갈 수 있습니다. 먼저 임의의로 범위 내에서 4의 값을 테스트해봅니다. 

만약 주어진 n이 10보다 크다면, 4보다 작은 값은 살펴볼 필요가 없습니다. 4보다 작은 값들은 10개의 코인보다 적은 코인이 필요할 것이 자명하기 때문입니다. 그래서 아래 그림과 같이 탐색범위를 줄일 수 있습니다.

반대로 주어진 n이 10보다 작다면, 4보다 큰 값들은 찾아보지 않아도 됩니다.

이러한 방식과 유사한 탐색 방법이 있습니다. 바로 이진 탐색 기법입니다. 이진 탐색을 적용하기 위해서 탐색할 범위를 설정하는 것이 필수입니다. 위 간단한 예시에서도 범위가 있다는 가정을 했었습니다. 현재 문제에서는 어떻게 범위를 정할 수 있을까요.

 

심플하게 생각해서 입력으로 들어온 n을 탐색 범위의 최대 값으로 생각할 수 있습니다. 아무리 값이 커 봐야 n보다 작은 값이 답으로 나올 것은 자명하기 때문에 n을 최대 값으로 설정해도 될 것 같습니다.

var arrangeCoins = function(n) {
    let left = 0,
        right = n;
    
    // Low Bound
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        const needCoin = sigmaN(mid);
        
        if (needCoin < n) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    if (sigmaN(left) === n) { return left; }
    else { return left-1; }
};

function sigmaN(n) {
    return n*(n+1)/2
}

이진 탐색을 이용하면 반복문 한 스텝을 통해 탐색범위를 절반씩 줄여갈 수 있기 때문에 O(logn)의 시간 복잡도로 문제를 풀 수 있습니다.

 

Github: 441.js

GitHub - opwe37/Algorithm-Study