본문 바로가기

전체 글131

[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.
[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] 3Sum (javascript) 주어진 숫자 배열에서 3개의 숫자를 조합하여 0이 되는 조합을 찾아내는 문제다. 1. 같은 숫자가 여러개 있다면, 여러번 사용되어도 된다. 2. 결과 조합에는 중복이 없어야 한다. 코드가 굉장히 지저분하게 작성되었다ㅜㅜ 3중 포문이 웬말이냐... /** * @param {number[]} nums * @return {number[][]} */ var threeSum = function (nums) { nums.sort((a, b) => a - b); // 오름차순 정렬 // 0을 제외하고, 중복되는 숫자는 최대 2개만 있어도 된다. const uniq = [...new Set(nums)]; const newArr = []; for (let i = 0; i < uniq.length; i++) { const.. 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.
[LeetCode] 2. Add Two Numbers (javascript) 두 Linked List를 더해주는 문제다. 리스트가 integer 크기 제한보다 길 때도 있으므로 BigInt를 사용했다. /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function (l1, l2) { let l = ''; let ll = ''; while (l1) { l = l1... 2021. 5. 31.
[LeetCode] 200. Number of Islands (javascript) 주어진 2차 배열에서 "1"은 육지, "0"은 바다를 나타낸다. 육지 덩어리의 갯수를 세는 문제다. 1을 찾고, 그 1에 상하좌우로 연결된 1들을 재귀함수로 모두 찾아내어 -1로 바꾸어준다. 한 덩어리를 다 바꾸고나면 count++를 해준다. /** * @param {character[][]} grid * @return {number} */ var numIslands = function (grid) { const m = grid.length; // 4 max i const n = grid[0].length; // 5 max j let temp = grid; let index = findLandIndex(grid, m, n); let count = 0; while (index) { temp = checkF.. 2021. 5. 31.
[LeetCode] 12. Integer to Roman (javascript) 주어진 숫자를 로마자로 변환하는 문제다. 1~3999의 숫자만 변환할 수 있으면 된다. 1의 자리, 10의 자리, 100의 자리, 1000의 자리에서 사용되는 문자열의 종류를 정의해주고, 0~9의 숫자 표현법을 패턴화하여 더해주도록 했다. /** * @param {number} num * @return {string} */ var intToRoman = function(num) { // num은 1~3999이다. const arr = num.toString().split('').reverse(); let result = ''; for (let i = 0; i < arr.length; i++){ result = makeRoman(parseInt(arr[i]), i) + result; } return res.. 2021. 5. 31.
[LeetCode] 43. Multiply Strings (javascript) 주어진 숫자 문자열들을 곱하는 문제다. BigInt를 사용하면 아주 쉽게 풀 수 있다. /** * @param {string} num1 * @param {string} num2 * @return {string} */ var multiply = function(num1, num2) { return (BigInt(num1) * BigInt(num2)).toString(); }; 2021. 5. 31.