99클럽 코테 스터디 30일차 TIL | Arranging Coins

🖥️ 문제

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Example 1:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

📝 풀이

class Solution {
    public int arrangeCoins(int n) {
        int left = 0;
        int right = n;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            long coinsNeeded = (long) mid * (mid + 1) / 2;

            if (coinsNeeded == n) {
                return mid;
            } else if (coinsNeeded < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
}

문제는 주어진 동전 n을 사용하여 최대 몇 개의 완전한 행을 만들 수 있는지 찾는 문제다. 해당 문제는 이진 탐색을 사용하여 범위를 좁혀가면서 목표 값을 찾았고, 문제를 푸는 순서는 k가 될 수 있는 범위를 설정하고, 중간 값을 계산하여 필요한 동전 수와 비교했다.

🤔 고찰