본문 바로가기

JavaScript8

[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 < count; i++){ const item = nums.shift(); const index = nums.findIndex((n)=> n===item); if(index > -1) { nums.splice(index, 1); } else {.. 2021. 6. 11.
[Javascript] 이벤트루프와 호출 스택(call stack), 비동기성 자바스크립트의 큰 특징으로 비동기성과 싱글스레드, Non-blocking IO가 있다. 비동기성은 알겠고, 논 블로킹 IO도 비동기성에서 오는 특징이라는건 알겠는데, 비동기성은 어떻게 동작하는 것일까? 그것도 싱글스레드라면, 한번에 한 동작밖에 못하는게 아닌지? 우선 동기성과 비동기성은 간단히 그림으로 살펴보자. 한 동작을 수행하다가 다른 동작이 필요한 경우, 동기 : 응답이 반환될때까지 하던 일을 멈추고 기다린다. 비동기 : 응답을 기다리느라 하던 일을 멈추지 않는다. 여기서 언뜻 들었던 의문이 있다. 하던 일을 멈추지 않는다 = 여러 일을 동시에 한다 => 싱글스레드인데? 이 부분은 자바스크립트의 동작 원리, 특히 이벤트루프와 호출스택을 이해해야 한다. 호출 스택(call stack) 자바스크립트는 .. 2020. 4. 3.