99클럽 코테 스터디 29일차 - 이진탐색

Arranging Coins

풀이

• n에서 차감하면서 만들 수 최대 row를 만든다.
• 이진탐색의 경우, mid 값을 뽑아 mid까지 모든 수를 더해 n과 비교한다. n보다 작을 경우, 해당 row는 모두 채울 수 있으므로 low를 올린다. 모두 더한 값이 n일 경우 mid까지 채울 수 있으니 mid를 반환,

코드 - 순회

class Solution {
    public int arrangeCoins(int n) {
        int c = 0;
        int row = 0;
        
        while(c <= n){
            c++;
            n -= c;
            row++;
        }
        return row;
    }
}

코드 - 이진탐색

class Solution {
    public int arrangeCoins(int n) {
        long low = 1;
        long high = n;    
        
        while(low <= high) {
            long mid = ((low + high) / 2);
            long sum = mid * (mid+1) / 2;
            
            if(sum == n) {
              return (int) mid;
            } else if(sum < n) {
              low =  mid +1;        
            } else {
              high =  mid -1;
            }
        }
        
        return (int) high;
    }
}

정리

• 이진탐색 문제인데 도저히 이진탐색으로는 생각이 나지 않아 선형순회로 풀었음..