Published:
Updated:

  • Reference
  • μ‹œκ°„λ³΅μž‘λ„: $O(N)$
  • Runtime 168ms
  • Beats 76.91%


Solution

from typing import List


class Solution:
    # κ·Έλƒ₯ λ‹¨μˆœν•˜κ²Œ λ°”λ‘œ μ „ ν–‰μ˜ (ν˜„μž¬μ™€ λ°”λ‘œ μ „μ˜ μ—΄)을 μΆ”κ°€ν•΄λ‚˜κ°€λ©΄ 됨
    def generate(self, numRows: int) -> List[List[int]]:
        # 항상 첫 번째 행은 1
        pascal = [[1]]

        # κ·Έ λ‹€μŒ ν–‰κΉŒμ§€ λΉ„κ΅ν•˜λŠ” κ±°λ‹ˆκΉŒ 1을 μ•ˆ λΉΌμ£Όλ©΄ λ²”μœ„ μ—λŸ¬
        for i in range(numRows - 1):
            # tmp ν–‰ μ €μž₯ν•˜κ³  계속 μ΄ˆκΈ°ν™”μ‹œν‚΄ (λ˜‘κ°™μ΄ 항상 첫 번째 행은 1)
            tmp = [1]  # 처음의 1

            # jκ°€ 0μ—μ„œ iκΉŒμ§€μ˜ λ²”μœ„μ— μžˆμ„ λ•ŒκΉŒμ§€(μ •μ‚Όκ°ν˜•) μ•„λž˜λ₯Ό 반볡
            for j in range(0, i):
                # i ν–‰μ˜ j번째 μš”μ†Œμ™€ j+1번째 μš”μ†Œλ₯Ό λ”ν•œλ‹€λŠ” 것은
                # μœ„μ—μ„œ μ„€λͺ…ν•œ κ²ƒμ²˜λŸΌ λ°”λ‘œ μ „ ν–‰μ˜ (ν˜„μž¬μ™€, λ°”λ‘œ μ „μ˜ μ—΄)을 μΆ”κ°€ν•˜λŠ” 것과 λ˜‘κ°™μ€ μ†Œλ¦¬ (λ’€μ§‘μ–΄μ„œ)
                tmp.append(pascal[i][j] + pascal[i][j + 1])

            # λ§ˆμ§€λ§‰μ˜ 1
            tmp.append(1)
            # ν•œμ€„μ΄ μ™„μ„±λμœΌλ‹ˆ 이걸 계속 μΆ”κ°€ν•΄λ‚˜κ°€λ©΄ μ‚Όκ°ν˜• μ™„μ„±
            pascal.append(tmp)

        return pascal


print(Solution().generate(5))
print(Solution().generate(1))

Leave a comment