LeetCode: 441. Arranging Coins

https://leetcode.com/problems/arranging-coins/description/

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

 

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.
 

Constraints:
1 <= n <= 231 - 1

 

풀이

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var n = n
        var count = 0
        
        if n < 3 { return 1 }
        
        for i in 1 ... n {
            let num = n - i
            
            if num >= 0 {
                n = num
                count += 1
            } else {
                break
            }
        }
        
        return count
    }
}

// 다른 사람 풀이
class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var value = 1
        var n = n

        while n > value {
            n = n - value
            value += 1
        }

        if n < value && n > 0 {
            return value - 1
        } else {
            return value
        }
    }
}

다른 사람 풀이가 속도가 월등히 뛰어난 걸 보고, 어떤 차이가 있길래 이렇게 차이가 클까 싶어 생각해봤다.

시간복잡도는 동일하지만 내 구조는 for문을 돌면서 if 조건에 맞는지 확인하고 다른 사람 코드는 while에서 한번에 조건에 부합하는 때에만 명령을 수행하는 구조이다. 

앞으로는 for문과 if, break 형식을 while로 바꿀 수 있는지 더 고민 해보아야 겠음.

---

import Testing

struct Tests {
    private let solution = Solution()
    
    @Test func test1() async throws {
        #expect(solution.arrangeCoins(13) == 4)
    }
    
    @Test func test2() async throws {
        #expect(solution.arrangeCoins(8) == 3)
    }
    
    @Test func test3() async throws {
        #expect(solution.arrangeCoins(5) == 2)
    }
    
    @Test func test4() async throws {
        #expect(solution.arrangeCoins(4) == 2)
    }
    
    @Test func test5() async throws {
        #expect(solution.arrangeCoins(3) == 2)
    }
    
    @Test func test6() async throws {
        #expect(solution.arrangeCoins(2) == 1)
    }
}