[Java] LeetCode 441 : Arranging Coins

LeetCode # 441

---

 

 

Example 1:

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

 

Example 2:

Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.

 

Note:

• 1 <= n <= 2³¹ - 1

---

Solution #1 (5ms)

class Solution {
    public int arrangeCoins(int n) {
        if(n<=1) return n;
        int i = 1;

        while (n>=0){
            n = n - i;
            i++;
        }
        return i - 2;
    }
}

 

Result #1

💡 반복문을 통해 입력값 n이 음수가 될 경우의 i 값을 구한다.

i는 1부터 시작해서 반복문이 돌 때마다 1씩  증가시킨다. 입력 값 n에 i를 빼고, n이 음수가 될 경우의 i -2 값이 정답이다. 직관적인 풀이 방법이지만 효율은 좋지 않다.

---

Solution #2 (1ms)

class Solution {
    public int arrangeCoins(int n) {
        if (n <= 1) return n;

        int left = 0, right = n;

        int answer = 0;
        while (left <= right) {
            int m = (left + right) / 2;
            long sum = (long) m * (m + 1) / 2;
            if (sum <= n) {
                answer = m;
                left = m + 1;
            } else {
                right = m - 1;
            }
        }
        
        return answer;
    }
}

 

Result #2

💡 등차수열의 합 공식 + 이진 탐색을 통해 답을 구한다.

등차수열의 합 공식은 위와 같다. 입력값 n보다 작거나 같은 k의 최댓값을 구하는 것이 문제이다.

빠른 속도로 구하기 위해 이진 탐색을 이용한다.

 

1) left 값과 right 값을 초기화한다. 초기 값은 0 과 n 이다.

2) left 와 right 의  중간 값 m 을 구한다.

3) 등차수열의 합 공식을 이용해서 1 에서 m 까지 더한 값 sum 을 구한다.

4) sum 과 입력값 n 을 비교한다.

 

1. sum 이 입력값 n 보다 작을 경우, 조건에는 만족하므로 우선 m 을 answer 에 대입한다. 하지만 우리가 구해야 할 것은 최댓값이므로 m 보다 더 큰 값으로도 조건이 만족하는지 검사해야한다. 따라서 left 값을 m+1 값으로 바꿔서 검사 범위를 축소 시킨다. (m+1 ~ right)
2. sum 이 입력값 n 보다 클 경우, 조건에 만족하지 않는다. right 값을 m-1 값으로 바꿔서 검사 범위를 축소시킨다. (left ~ m-1)

5) 이것을 right 값이 left 값보다 작아질 때까지 반복시킨다.

---

 

More Algorithm!

 

👇👇

 

github.com/ggujangi/ggu.leet-code

ggujangi/ggu.leet-code

 

 

 

출처 : leetCode