99클럽 코테 스터디 30일차 TIL (이분탐색)

JAVA / Lv 0. Arranging Coins 

 

문제

당신은 동전을 n개 가지고 있고 이 동전으로 계단을 만들고 싶어합니다. 계단은 k행으로 구성되어 있으며 행에는 정확히 동전이 있습니다. 계단의 마지막 행은 불완전 할 수 있습니다.

정수가 주어지면 n, 만들 계단의 완전한 행의 수를 반환합니다 .

 

제한사항

• 1 <= n <= 231 - 1

 

입출력 예

 

문제 해결

중간행을 구하고
(left + right) / 2;

중간행까지 더합니다. (등차수열)
(long) mid * (mid + 1) / 2;

더한 값이 n보다 작거나 같으면 즉, 주어진 동전보다 작거나 같게 사용해서 하나의 행을 완성시켰습니다.
그렇다면 그 행을 answer에 update 시키고 더 큰 수를 찾으러 떠나기 위해 다음 행으로 +1 해줍니다.

반면, 주어진 동전보다 많게 사용하려하면 mid값이 크다는 의미이므로 mid - 1 해줍니다.
해당 조건들을 계속 반복하다보면 왼쪽 오른쪽의 폭이 점점 줄어들고 left, right가 같아진다면
로직은 종료가 됩니다.

나의 풀이

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

        int answer = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            long k = (long) mid * (mid + 1) / 2;

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

        return answer;
    }
}