본문 바로가기

🏃 algorithm/leetcode93

LeetCode 120 - Triangle (Medium) 문제 LeetCode - 120번 풀이 과정 첫번째 행에서 마지막 행까지 도달하기 위한 거리의 최소 합을 구하는 문제입니다. dp(row, idx) = row 행의 idx 열에서 마지막 행에 도달하기 위한 최소 거리 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[row][idx] = min(dp[row + 1][idx], dp[row + 1][idx + 1]) + triangle[row][idx] 코드 /** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function (triangle) { const INF = 9999999; const rowLimit = triangle.length; const mem.. 2021. 4. 13.

LeetCode 38 - Count and Say (Medium) 문제 LeetCode - 38번 풀이 과정 주어진 규칙대로 문자열 처리를 구현하는 문제입니다. 연속된 숫자들의 개수를 세어주기 위해 임시 변수를 사용했습니다. 코드 /** * @param {number} n * @return {string} */ var countAndSay = function (n) { let str = "1"; for (let i = 1; i < n; i += 1) { let cacheKey = ""; let count = 0; let temp = ""; for (let ch of str) { if (cacheKey !== ch) { if (cacheKey) { temp += `${count}${cacheKey}`; } cacheKey = ch; count = 1; } else { c.. 2021. 4. 13.

LeetCode 199 - Binary Tree Right Side View (Medium) 문제 LeetCode - 199번 풀이 과정 이진 트리를 오른쪽에서 봤을 때 보이는 노드들을 높이순으로 출력하는 문제입니다. 이를 위해서 방문 시 이전까지 방문한 트리 높이 추적을 위해 isVisitedLevel 이라는 배열을 유지하며 방문을 오른쪽 자식 -> 왼쪽 자식 순으로 하되 이전에 방문하지 않은 레벨일 경우에만 배열에 push 해줍니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefin.. 2021. 4. 5.

LeetCode 344 - Reverse String (Easy) 문제 LeetCode - 344번 풀이 과정 in place 한 방법으로 배열을 뒤집는 연산을 수행하는 문제입니다. 왼쪽 끝 과 오른쪽 끝 을 가리키는 두 개의 포인터를 활용해서 뒤집기 연산을 수행하면 됩니다. 코드 /** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString = function (s) { let lo = 0; let hi = s.length - 1; while (lo < hi) { [s[hi], s[lo]] = [s[lo], s[hi]]; lo += 1; hi -= 1; } return s; }; 2021. 4. 5.

LeetCode 1578 - Minimum Deletion Cost to Avoid Repeating Letters (Medium) 문제 LeetCode - 1578번 풀이 과정 연속된 문자열에서 인접한 각 쌍의 문자가 서로 달라야 하는데 필요한 보정 값을 구하는 문제입니다. 때문에 각 문자를 하나씩 순회하며 같은 문자로 이루어진 인접한 그룹들을 찾고, 이 그룹 내에서 가장 비용이 큰 문자를 제외하고 다른 모든 문자들을 선택해서 제거하면 됩니다. 저 같은 경우 각각의 그룹을 먼저 만들고 비용을 계산했는데, 사실 이럴 필요없이 그냥 각 문자를 순회하며 인접한 문자들이 서로 같을 때 그때그때 그룹을 만들어서 비용을 체크해줘도 됩니다. 코드 /** * @param {string} s * @param {number[]} cost * @return {number} */ var minCost = function (s, cost) { const .. 2021. 3. 8.

LeetCode 904 - Fruit Into Baskets (Medium) 문제 LeetCode - 904번 풀이 과정 최대 2종류의 과일을 담을 수 있는 바구니를 이용해서 가능한 많은 과일을 담은 경우를 찾는 투 포인터 문제입니다. head 와 tail 을 이용해서 과일을 하나씩 순회하는데, 2종류의 제약조건을 만족시키는 과일이면 tail 을 증가시키고 그렇지 않을 경우 이를 만족할때까지 head 를 증가시키는 방법을 이용해서 구현합니다. 코드 /** * @param {number[]} tree * @return {number} */ var totalFruit = function (tree) { let head = 0; let tail = 0; let answer = 1; const basket = new Map(); basket.set(tree[head], 1); while.. 2021. 3. 8.

이전 1 2 3 4 5 6 7 ··· 16 다음

티스토리툴바