본문 바로가기

leetcode87

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 787 - Cheapest Flights Within K Stops (Medium) 문제 LeetCode - 787번 풀이 과정 최대 K 개의 경유지를 포함한다는 조건 아래에서 한 정점에서 목표 정점까지의 최단 경로를 구하는 문제입니다. 따라서 단일 정점 - 모든 쌍 최단 경로 알고리즘인 다익스트라 알고리즘 을 변형해서 문제를 해결하였습니다. 사실 간선 선택을 위해 우선순위 큐 도 사용하지 않아서 애매한 부분이 있지만 BFS + Dijkstra 의 유형이라고 생각하면 될 것 같습니다. 이 문제의 핵심은 k 개의 경유지를 어떻게 처리할 것인가 입니다. 기존의 다익스트라 알고리즘 은 이전에 발견되어 큐에 저장되어 있는 경로 중 더 짧은 경로가 발견되어 dist 가 갱신 되었을 경우 큐에서 이전에 발견된 경로가 pop 되어 처리할 차례가 되면 그냥 무시를 해주는 방식으로 처리를 해줬습니다. .. 2021. 3. 2.
LeetCode 417 - Pacific Atlantic Water Flow (Medium) 문제 LeetCode - 417번 풀이 과정 입력으로 주어진 격자판에서 가장자리에 도달할 수 있는 좌표를 찾는 BFS 문제였습니다. 문제 조건에 따라 x 죄표 혹은 y 좌표 가 0보다 작아질 경우는 pacific 에 해당하고 그 반대의 경우에는 atlantic 에 해당합니다. 따라서 matrix 의 각 지점마다 BFS 를 수행하며 pacific 과 atlantic 에 모두 도달 가능한 경우에만 해당 죄표값을 기록하여 답을 구할 수 있습니다. 이때 인접한 지역에 대해서 값이 같거나 작을 경우에만 이동할 수 있다는 것에 유의하도록 합니다. 코드 /** * @param {number[][]} matrix * @return {number[][]} */ var pacificAtlantic = function (m.. 2021. 3. 2.
LeetCode 17 - Letter Combinations of a Phone Number (Medium) 문제 LeetCode - 17번 풀이 과정 휴대폰 자판을 이용해서 만들 수 있는 문자열을 모두 찾는 백트래킹 문제입니다. 각 숫자별로 할당된 문자들을 표현해주는 다양한 방법들 (Map, Object 등) 이 있지만 저는 배열에 인덱스로 접근하는 방법을 사용했습니다. 숫자로 이루어진 주어진 입력 문자열을 한 자리씩 순회하며 만들 수 있는 모든 문자열을 재귀호출로 생성하면 됩니다. 코드 /** * @param {string} digits * @return {string[]} */ const buttons = [ 0, 0, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", ]; var letterCombinations = function (digits) {.. 2021. 3. 2.
LeetCode 230 - Kth Smallest Element in a BST (Medium) 문제 LeetCode - 230번 풀이 과정 이진 검색 트리 에서 k번째 원소를 찾는 문제입니다. 이진 검색 트리 는 루트 노드가 해당 노드의 왼쪽 자식 노드보다 크고 오른쪽 노드보다 작은 값을 가집니다. 따라서 이를 중위 순회 할 경우 키 값이 정렬된 순서대로 방문한다는 것을 알 수 있습니다. 이를 활용하여 중위 순회를 하는 함수를 만들고 k 번째 노드에 방문했을 때를 기록하여 답을 구하도록 하였습니다. 코드 /** * @param {number[]} nums * @return {number} */ var rob = function (nums) { const memo = new Array(nums.length).fill(-1); function dp(i) { if (i >= nums.length) re.. 2021. 3. 2.

티스토리툴바