본문 바로가기

leetcode15

[LeetCode] Minimum Path Sum (javascript) 좌상단에서 출발하여 우하단까지 오른쪽, 아래로만 움직여 도착해야 한다. 가는 경로의 숫자를 모두 더했을때, 가장 작은 숫자를 구하는 문제다. 최단경로 경우의 수 문제와 유사하게 풀 수 있다. 처음엔 모든 경로를 처음부터 더해가면서 최솟값을 구해보려고 했으나.. (첫번째 경로 결과 : 10, 두번째 경로 결과 : 8 ...) Time Limit에 걸렸다. 이미 구해놓은 결과값보다 큰 경우 패스하도록 해도 마찬가지... 더보기 틀린 풀이 // 잘못된 접근방식(Time Limit) var minPathSum = function (grid) { let result = Infinity; const ml = grid.length - 1; const nl = grid[0].length -1; console.log(m.. 2021. 6. 22.
[LeetCode] Merge Intervals (javascript) 주어진 2차배열 내의 요소들끼리 겹치는 것을 합쳐주는 문제다. 예를들어 [[1, 3], [2, 4], [5, 8]] 이 있다고 하면 이렇게 [[1, 4], [5, 8]]로 겹치는 요소는 합쳐주는 것이다. 여기서 각 요소의 첫 번째 요소([1, 4]의 1)를 head, 두 번째 요소([1, 4]의 4)를 tail이라고 부르겠다. 그래서 배열을 차례대로 돌면서, 현재 요소와 다음 요소가 겹치는 부분이 있으면 합치는 방식으로 풀었다. 어렵지 않게 풀리는듯 했으나 간과했던 포인트가 있었는데, 1. 주어진 배열들은 소팅되어 있지 않다. 즉, 차례대로 합치다간 나중에 제외되는 요소가 나타난다. ex. [[1, 3], [2, 4], [5, 8], [2, 3]] => [[1, 4], [5, 8]]이 되어야 하나 [[1.. 2021. 6. 15.
[LeetCode] Unique Paths, Unique Paths II (javascript) Unique Path 전형적인 최단경로 찾기 조합 문제! (m + n)! / m! * n! 식을 이용하여 풀었다. /** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { // (m+n-2)! / ((m-1)! * (n-1)!) console.log(factorial(m+n-2), factorial(m-1), factorial(n-1)) return factorial(m+n-2)/(factorial(m-1)*factorial(n-1)); }; const factorial = (n) => { if(n == 0) return 1; let num = n; for (let i = num -.. 2021. 6. 15.
[LeetCode] Longest Substring Without Repeating Characters (javascript) 가장 긴 반복되지 않는 문자열의 길이를 리턴하는 문제다. 예를들어 abcdaddd => [abcd][ad][d][d] = 4 abcabc => [abc][abc] = 3 처음엔 문자별로 for문을 돌면서 다음에 출현하는 같은 문자까지의 index 차이를 구하려고 했다. abcabc => [abc] "a"bc => 3 다만 이런경우... abbabc => [abb] "a"bc => 3 이런 케이스를 피할 수 없고, 또 abb안에서 중복이 없는지 검사하는 등 복잡해지게 된다. 다른 풀이들을 참고한 결과, substring해가면서 중복이 없으면 결과값에 더해주고, 중복이 있으면 앞글자를 방출하는 형태가 가장 이해하기도 편하고 코드도 깔끔해 보여서 이렇게 구현했다. /** * @param {string} s *.. 2021. 6. 15.
[LeetCode] Longest Substring Without Repeating Characters (javascript) 반복되지 않는 가장 긴 문자열의 길이를 찾는 문제다. 예를들어 abcabcda 라면, abcd or bcda = 4가 된다. current라는 문자열 변수를 두고 현재 문자열에 포함되지 않은 문자라면 더해가면 되고, 포함되어 있다면 잘라내면 된다. current = "abc" 인 상태에서 다음 a가 들어오게 되면 current에 존재하는 a의 index를 찾아 그 다음부터 잘라내고, current.substring(2), current = "bc" 다음으로 들어온 a를 더해준다. current += "a", current = "bcd" /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { if .. 2021. 6. 11.
[LeetCode] Repeated String Match (javascript) 주어진 문자열 a, b가 있을 때, a를 몇번 반복해야 b가 한번이라도 포함되는지 찾는 문제다. 처음엔 별생각 없이 str.includes(b) 대신 new RegExp(b).test(str) 를 사용해 풀었었다. 그러나 정규식보다 includes가 훨씬 빨랐다. // 정규식보다 includes를 쓰는게 런타임도, 메모리도 훨씬 낫다 // 정규식 : Runtime 340ms, Memory 45MB // includes : Runtime 84ms, Memory 40.4MB /** * @param {string} a * @param {string} b * @return {number} */ var repeatedStringMatch = function(a, b) { let str = a; let count .. 2021. 6. 11.
[LeetCode] Single Number (javascript) 주어진 배열에서 하나만 존재하는 숫자를 찾아 리턴하는 문제다. 배열에서 숫자를 하나씩 꺼내가면서, 남은 배열에 같은 숫자가 존재하지 않는 경우 리턴한다. 존재하는 경우, splice로 확인한 숫자를 제거한다. /** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { const count = Math.floor(nums.length/2); for(let i = 0; i n===item); if(index > -1) { nums.splice(index, 1); } else {.. 2021. 6. 11.
[LeetCode] Generate Parentheses (javascript) 가능한 모든 괄호 조합을 중복없이 리턴하는 문제이다. 유효한 괄호조합 판별(Valid Parentheses) + 조합 같은 느낌의 문제이다. 굉장히 까다로울 걸로 생각했으나, Valid Parentheses 문제를 풀어봤다면(유효한 괄호조합 판별법을 안다면) 크게 어렵지 않았다. (Valid Parentheses 문제 : https://leetcode.com/problems/valid-parentheses/) 유효한지 확인하는 방법은 스택을 활용하면 된다. /** * @param {number} n * @return {string[]} */ var generateParenthesis = function (n) { if (n === 1) return ['()']; let result = ['(']; // .. 2021. 6. 8.
[LeetCode] 104. Maximum Depth of Binary Tree (javascript) 이진트리에서 가장 깊은 노드의 깊이를 구하는 문제이다. 깊이우선탐색으로 구할 수 있다. /** * 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===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { let depth = 0; const dfs = (root, len) =.. 2021. 5. 31.

티스토리툴바