Leetcode 441. Arranging Coins - 파이썬

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Arranging Coins
등급: Easy

내용: 

n coin이 주어지는데 그것으로 계단을 만들어라. 마지막 계단층에 충분한 코인이 없다면, 그 계단은 제외하고 총 몇 개의 계단이 있는가?

 

<코드>

class Solution(object):
    def arrangeCoins(self, n):
        # iterative solution
        # ans is for number of rows
        ans = 0
        row = 1
        while n > 0:
            n -= row
            # add one more space to the row
            row += 1
            
            # add one more for the answer
            ans += 1
            
        # if incomplete row
        if n < 0:
            return ans - 1
        
        return ans
        """
        :type n: int
        :rtype: int
        """

<논리>

간단하다. 큰 설명은 필요없을 듯 하다.

 

<better>

class Solution(object):
    def arrangeCoins(self, n):
        # binary search solution
        left, right = 0, n
        while left <= right:
            k = (right+left) // 2
            curr = k* (k+1) // 2
            if curr == n:
                return k
            if n < curr:
                right = k-1
            else:
                left = k+1
        return right
        """
        :type n: int
        :rtype: int
        """

 

 

<총평>

 

Happy coding!