[코테] 리트코드 파이썬 139번 Word Break, 152번 Maximum Product Subarray

139번 Word Break

Word Break - LeetCode

 

주어진 문자열 리스트만을 이용해서, 문자열s를 만들 수 있는 지에 대한 여부를 리턴하는 문제이다.

 

주어진 리스트에서 가장 긴 문자열의 길이를 저장한다. s의 처음 인덱스부터 1씩 늘려가며 해당되는 substring이 리스트에 있는지 확인한다. (j,i) -> (0,1)-> (1,2) (0,2)-> (2,3) (1,3) (0,3)

겹치는 문자열이 있으면 해당 i 인덱스까지의 dp[i]를 true로 둔다. dp의 마지막 인덱스가 true면 true, false면 false를 출력한다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        max_len = max(map(len, wordDict))

        for i in range(1, n + 1):
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break

        return dp[n]

---

152번 Maximum Product Subarray

Maximum Product Subarray - LeetCode

 

정수 리스트의 subarray의 곱 중에서 가장 큰 곱의 값을 리턴하는 문제이다.

subarray를 구하는 것이기 때문에 중간에 뛰어넘어서 곱을 하는 것은 허용되지 않는다. 그렇기 때문에 주어진 리스트를 순회하며 다음 인덱스에 해당하는 값을 곱하여 현재 최댓값과 현재 최솟값을 구한다. 현재 최댓값과 저장된 최댓값을 비교했을 때 큰 값을 저장하여 출력한다.

이때 최솟값을 저장하는 이유는 음수가 포함된 리스트가 나올 경우 음수가 곱해지면 양수가 되어 최대곱이 될 가능성이 있기 때문이다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:

        curMaxValue, curMinValue = 1, 1
        maxProduct = nums[0]

        for num in nums:
            curMaxProduct = curMaxValue * num
            curMinProduct = curMinValue * num

            curMaxValue = max(curMaxProduct, curMinProduct, num)
            curMinValue = min(curMaxProduct, curMinProduct, num)

            maxProduct = max(maxProduct, curMaxValue)
        return maxProduct