[leetcode] 22, 29, 53, 66

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

My Answer 1: Accepted (Runtime: 64 ms - 78.24% / Memory Usage: 15.1 MB - 21.81%)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = max(nums)
        sub = 0
        for i in range(len(nums)):
            if sub + nums[i] >= nums[i]:
                sub += nums[i]
                ans = max(ans, sub)
            else:
                sub = nums[i]
        
        return ans

ans 는 nums 의 최댓값으로 default 설정

sub 에 값을 하나씩 더해가면서
지금까지의 합이 자기 자신보다 큰 경우만 ans update
자기 자신보다 작아지면 볼 필요가 없으므로 sub = nums[i] 로 초기화

---

66. Plus One

https://leetcode.com/problems/plus-one/

My Answer 1: Accepted (Runtime: 28 ms - 90.03% / Memory Usage: 14.2 MB - 48.02%)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if digits[-1] < 9:
            digits[-1] += 1
            return digits
        
        digits[-1] = 0
        carry = 1
        for i in range(len(digits)-2, -1, -1):
            if digits[i] + carry <= 9:
                digits[i] += carry
                carry = 0
            else:
                digits[i] = (digits[i] + carry) % 10
        
        if carry:
            digits.insert(0, 1)
        
        return digits

마지막 자리의 값이 9 보다 작으면 그냥 1 더해서 return

9 라면 마지막 자리는 0 으로 & carry 는 1 로 설정하고
바로 앞자리부터 역순으로 보면서 carry 와 더한 값이 9 이하인지 확인

9 이하면 그대로 carry 더해주고 carry 는 0 으로 초기화
9 보다 커지면 나머지 값으로 바꿔주고 carry 는 그대로 1

다 보고도 carry 가 남아있으면 맨 앞에 1 추가

---

22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

My Answer 1: Accepted (Runtime: 36 ms - 64.52% / Memory Usage: 14.7 MB - 11.60%)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def func(o, c, p):
            if o == 0 and c == 0:
                self.ans.append(p)
                return
            
            if o > 0:
                func(o-1, c, p + "(")
            if o < c and c > 0:
                func(o, c-1, p + ")")
        
        self.ans = []
        func(n, n, "")
        
        return self.ans

재귀로 가능한 괄호 조합을 찾아줌

o(pen), c(lose) 를 이용해서
open 할 수 있으면 (if o > 0) o-1 & open~
close 는 open 한 게 있어야 가능하니까 o < c 일 때만 c-1 & close~

---

29. Divide Two Integers

https://leetcode.com/problems/divide-two-integers/

My Answer 1: Accepted (Runtime: 32 ms - 77.46% / Memory Usage: 14 MB - 93.97%)

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend / divisor < -2 ** 31:
            return -2 ** 31
        if dividend / divisor > 2 ** 31 - 1:
            return 2 ** 31 - 1
        
        return int(dividend / divisor)

첨엔 순환소수 그 문제인 줄 알고 트라우마 부활할 뻔..

범위 체크해주고 int() 형변환으로 truncate