본문 바로가기

🏃 algorithm/leetcode93

LeetCode 46 - Permutations (Medium) 문제 LeetCode - 46번 풀이 과정 주어진 배열로 순열을 만드는 문제입니다. 백트래킹 을 통해 배열의 요소들을 하나씩 순회하며 순열을 만들어주면 됩니다. 이때 배열 연산으로 push or pop 을 사용하지 않고 javascript 의 spread 연산자로 새로운 배열을 만들어 넘겨주는 방식을 사용했습니다. 코드 /** * @param {number[]} nums * @return {number[][]} */ var permute = function (nums) { const ans = []; function permutation(selected) { if (selected.length === nums.length) { ans.push(selected); return; } for (let i = .. 2021. 3. 3.

LeetCode 21 - Merge Two Sorted Lists (Easy) 문제 LeetCode - 21번 풀이 과정 병합 정렬 의 병합 과정을 직접 구현해보는 문제입니다. 병합 정렬 은 각각의 배열 요소를 균등하게 나누고 나누어진 배열을 정렬하여 합치는 분할정복 을 사용하는 정렬 알고리즘입니다. 두 배열이 모두 정렬된 상태이기 때문에 배열의 가장 앞 요소부터 서로 비교해주며 작은 요소들을 하나씩 추가해나가면 됩니다. 만약 둘 중 하나의 배열이 비어있을 경우에는 비어있지 않은 배열을 그대로 이어붙이면 됩니다. 입력으로 둘 중 한 배열이 비어있는 것이 존재할 수 있으므로 이 부분에 대해 별도의 예외처리를 진행해줬습니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = .. 2021. 3. 2.

LeetCode 240 - Search a 2D Matrix II (Medium) 문제 LeetCode - 155번 풀이 과정 이차원 배열에서 목표값이 존재하는지 판단하는 문제입니다. 그냥 브루트 포스 로 접근한다면 O(MN) 의 시간 복잡도로 해결할수도 있지만 좀 더 효율적인 탐색을 위해 이분 탐색 을 적용했습니다. 각 행이 오름차순으로 정렬되어 있다는 점을 이용해서 각 행마다 이분 탐색 을 수행해 원하는 값이 존재하는지 판단합니다. 코드 /** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function (matrix, target) { for (let row of matrix) { if (bisect(row, target)) return true; } r.. 2021. 3. 2.

LeetCode 155 - Min Stack (Easy) 문제 LeetCode - 155번 풀이 과정 스택 을 사용해서 min stack 을 구현하는 문제입니다. 단순하게 구현하면 최소값을 찾을 때마다 Math.min 을 사용할 수도 있지만 문제 조건과 같이 상수 시간에 최소값을 찾기 위해서는 다른 방법이 필요합니다. 이를 위해 두 개의 스택을 사용하여 값을 저장하도록 합니다. 하나는 들어온 순서대로 쌓아 올리는 스택이고 다른 하나는 이에 대응하여 현재까지의 최소값을 저장하는 스택으로 사용합니다. 예를 들어 1, 2, 0, 3 이 순서대로 입력된다고 한다면 두 개의 스택은 다음과 같은 상태를 가지게 됩니다. | 3 | | 0 | | 0 | | 0 | | 2 | | 1 | | 1 | | 1 | A 스택 B 스택따라서 minValue 를 통해 현재까지의 최소값을 .. 2021. 3. 2.

LeetCode 39 - Combination Sum (Medium) 문제 LeetCode - 39번 풀이 과정 중복 조합 을 만들어서 숫자들의 합이 target 이 되는 모든 경우를 찾는 문제입니다. 여기서 중복 조합 이란 서로 다른 n개를 중복을 허용하여 r 개를 선택하는 경우 를 말합니다. 이를 위해서는 백트래킹 을 활용해서 모든 조합을 탐색해주는 과정이 필요합니다. 기존 조합에서는 i 번쩨 숫자를 선택했을 경우 그 다음 숫자인 i + 1 번째 부터 하나씩 골라야하지만 중복을 허용하기 때문에 선택 시작점을 i 번째 부터 해주면 됩니다. 코드 /** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function (candidates,.. 2021. 3. 2.

LeetCode 20 - Valid Parentheses (Easy) 문제 LeetCode - 20번 풀이 과정 스택 을 활용하는 대표적인 괄호 쌍 맞추기 문제입니다. 닫는 괄호 가 나타났을 때 스택의 가장 위에 짝이 맞는 여는 괄호 가 존재하는지 판단하면 되는 문제입니다. 이번 문제를 통해 javascript 의 includes 메서드를 활용하는 방법을 알 수 있게 되었습니다. || 연산자로 or 처리 해주는 것이 코드도 길어지고 번거로웠는데 원하는 요소가 존재하는지 판단하는 includes 를 활용해서 쉽게 조건을 판단할 수 있었습니다. 코드 /** * @param {string} s * @return {boolean} */ function top(stack) { return stack[stack.length - 1]; } var isValid = function (s.. 2021. 3. 2.

이전 1 ··· 9 10 11 12 13 14 15 16 다음

티스토리툴바