[LeetCode] DP 기본 문제들2; Max Subarray Sum/Product, Longest Palindromic Substring, Word Break (JavaScript)

Youtube 코드 없는 프로그래밍 DP 플레이리스트 따라서,
LeetCode DP 중급 문제 풀이

DP 난이도가 조금 올라가니까,
Problem-SubProblem 나누는 것도 쉽지 않았다

문제 대부분 혼자서 해결하지 못했고,
강의 영상과 LeetCode Discuss 내용 참고해서 해결했다

코드 자체는 별거 없는데,
점화식을 만들고 풀이법을 생각하는 것이 미숙하면 상당히 어렵게 느껴지는 것 같다

53. Max Subarray Sum

문제 요약

• Subarray 유형의 가장 기본 문제
• 합이 가장 큰 Subarray를 찾으면 됨
• 공간 복잡도를 O(1)로 사용하기 위해 nums 배열에 구간합을 바로 기록
• 직전까지의 구간합이 음수면 새로 시작, 양수면 추가

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = (nums) => {
  for (let idx = 1; idx < nums.length; idx++) {
    nums[idx] = nums[idx - 1] < 0 ? nums[idx] : nums[idx] + nums[idx - 1];
  }
  return Math.max(...nums);
};

---

152. Max Product Subarray

문제요약

• 위의 단순 합에서 곱으로 연산만 바뀌는 문제

회고

• 기본 구조는 부분합 문제와 동일
• 부호가 바뀌면 최대값 <=> 최소값으로 바뀔 수 있다는 점을 생각해서 최대값과 최소값을 모두 저장하고 있어야 함
• 이 문제부터 머리가 잘 안돌아감..ㅠ

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxProduct = (nums) => {
  const first = nums[0];
  let totMax = first;
  let preMax = first;
  let preMin = first;
  for (let i = 1; i < nums.length; i++) {
    const curNum = nums[i];
    const curr = [preMax * curNum, preMin * curNum, curNum];
    preMax = Math.max(...curr);
    preMin = Math.min(...curr);
    if (preMax > totMax) totMax = preMax;
  }
  return totMax;
};

---

5. Longest Palindromic Substring

문제요약

• 특정 문자열 내부에 palindrome이 있다면
• 최대 길이를 가진 palindrome
• 문자열 s의 첫 위치부터 해당 위치를 중심으로 하는 palindrome 탐색
• 이때 palindrome 길이는 홀수인 경우, 짝수인 경우 두개를 찾고
• 그 중 긴 것을 local longest로 저장

회고

• 강의 내용대로 DP스러운 코드는 구현하기가 쉽지 않았고..
• 처음에 거의 시간초과에 가까운 코드를 만들고 다른 풀이들을 참고했다
• 구현하고 보니 이 코드가 DP가 맞나 싶은데,
• 어쨌든 runtime 100ms 내외로 시간 복잡도를 크게 줄일 수는 있었다

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = (s) => {
  const getPal = (left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return s.slice(left + 1, right);
  };

  let longest = "";
  for (let i = 0; i < s.length; i++) {
    const pal1 = getPal(i, i);
    const pal2 = getPal(i, i + 1);
    const pal = pal1.length < pal2.length ? pal2 : pal1;
    longest = longest.length < pal.length ? pal : longest;
  }
  return longest;
};

---

139. Word Break

문제요약

• wordDict 안에 있는 단어들을 조합해서 문자열 s를 만들 수 있는지
• wordDict 단어들은 사용횟수 무제한
• 점화식: 문자열 abc를 만들 수 있는 경우 = 단어 ab에 c를 합친 경우

회고

• 이 문제도 problem - subproblem 나누기가 어려워서 헤맸던 문제
• discuss와 다른 답안들 참고해서 좀더 runtime과 memory를 줄여보고자 했다

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
const wordBreak = function (s, wordDict) {
  const size = s.length;
  const memo = Array(size + 1).fill(false);
  memo[0] = true;

  const wordSet = new Set(wordDict);

  for (let start = 0; start < size; start++) {
    if (!memo[start]) continue;
    wordSet.forEach((word) => {
      if (s.slice(start).indexOf(word) === 0) {
        memo[start + word.length] = true;
      }
    });
  }
  return memo[size];
};