[Leetcode(릿코드)] 441. Arranging Coins (Easy)

Binarysearch 문제

leetcode.com/problems/arranging-coins/

Arranging Coins - LeetCode

---

문제

1+2+3..+k <= n에서 k의 최댓값을 구하는 문제이다

 

해결

2가지 방식으로 풀었다

Runtime은  1번 방식은 6ms / Binarysearch가 1ms 걸렸다

 

1. n보다 작을때까지 더하다가 i를 출력

public static int arrangeCoins(int n) {
    int i = 0;
    int result = n;
    while (true) {
        result = result - i;
        if (result <= i) break;
        i++;
    }
    return i;
}

 

 

2. binarysearch

중앙값을 구한 후, 1부터 가운데값까지의 합 n(n+1)/2과 n을 비교하여 left값과 right값을 수정한다

최종적으로 right가 k의 최대값이다

Test Case 중에 int 범위를 넘는 Case가 있어서 Long 타입으로 변환해주었다

public static int arrangeCoins_binarysearch(int n) {
    int left = 1;
    int right = n;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((mid * (mid + 1L)) / 2L <= n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}