본문 바로가기

🏃 algorithm/leetcode93

LeetCode 283 - Move Zeroes (Medium) 문제 LeetCode - 283번 풀이 과정 정렬을 수행한 뒤에 같은 키 값을 가지는 원소들의 순서가 뒤바뀌지 않는 것을 stable sort 라고 합니다. 이번 문제에서는 주어진 배열에서 0을 배열의 끝쪽으로 옮겨주되 그 순서가 뒤바뀌면 안되는 로직을 구현하였습니다. 이때 별도의 array 를 복사하여 구현하면 안되고 배열 내에서 정렬이 in-place 로 수행되어야하므로 삽입정렬을 활용하여 구현했습니다. 삽입 정렬 은 배열의 끝 원소부터 하나씩 자신의 위치를 찾아 삽입 해주는 방식을 사용하는데, 여기서는 0을 발견할 때마다 0이 위치할 수 있는 위치를 반복해서 찾음으로서 O(N^2) 의 시간 복잡도로 문제를 해결하였습니다. 코드 /** * @param {number[]} nums * @return {.. 2021. 3. 2.

LeetCode 678 - Valid Parenthesis String (Medium) 문제 LeetCode - 678번 풀이 과정 주어진 문자열에서 괄호쌍이 올바르게 짝지어졌는지 판단하는 문제입니다. 다만 이 문제에서는 와일드카드(*) 가 존재하여 약간의 다른 방식의 접근이 필요합니다. 우선 이 와일드카드를 어떤 식으로 처리할지 결정해야합니다. 각각의 와일드 카드는 ( 혹은 ) 혹은 빈칸 으로 사용될 수 있으므로 현재 괄호 스택을 가지고는 어떤 방식으로 사용해야할지 알 수 없습니다. 따라서 해당 와일드 카드는 다음 세 가지 경우로 사용 방법을 나눌 수 있습니다. * 보다 앞서 발견된 ( 문자의 ) 역할 * 보다 늦게 발견된 ) 문자의 ( 역할 아무 역할도 하지 않는 빈칸 다시 말해 ) 문자에 대응되는 ( 가 이전에 스택에 존재하지 않을 경우 * 를 대신 사용하도록 하면 됩니다. 따라서 큐.. 2021. 3. 2.

LeetCode 1094 - Car Pooling (Medium) 문제 LeetCode - 1094번 풀이 과정 문제 분류는 탐욕 알고리즘 이지만 입력 값의 범위가 크지 않기 때문에 브루트 포스 로도 충분히 해결할 수 있는 문제였습니다. 우리가 찾아야 하는 것은 한 시점에 필요한 최대 capacity 입니다. 따라서 시간을 0.5 단위로 증가시키며 겹치는 최대 구간을 찾도록 합니다. 이때 0.5씩 증가시켜준 이유는 거리가 1 단위이기 때문입니다. (저와 같은 방법으로 구현한 분의 코드를 보니 시작 지점을 포함하고 종료 시간을 제외하여 1씩 증가시켜도 되도록 구현한 방법이 있었는데 그게 더 간단해보입니다.) 코드 /** * @param {number[][]} trips * @param {number} capacity * @return {boolean} */ var car.. 2021. 3. 2.

LeetCode 49 - Group Anagrams (Medium) 문제 LeetCode - 49번 풀이 과정 주어진 입력에서 Anagram을 찾는 문제입니다. Anagram은 순서에 상관없이 두 단어를 구성하는 문자의 종류와 개수가 동일한 관계를 말합니다. Anagram을 판단하는 직관적인 방법은 두 단어를 정렬한 뒤 같은 지 비교하는 것입니다. Javascript 에서 String 을 정렬하기 위해서는 spread 연산을 통해 Array로 바꿔준 이후 sort 함수를 사용합니다. 코드 /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function (strs) { const anagram = new Map(); for (let word of strs) { let sorted = [... 2021. 3. 2.

LeetCode 200 - Number of Islands (Medium) 문제 LeetCode - 200번 풀이 과정 섬의 개수를 세어주는 DFS 탐색 문제입니다. 간단한 문제이지만 히든 케이스 때문에 조금 헤맸습니다. LeetCode 문제는 깔끔하지만 입력 제한 사항이 명시되어있지 않은 경우가 있어서 난감한 상황이 종종 발생하는 것 같습니다. (입력으로 주어지는 grid 가 비어있는 경우가 존재할 것이라고 생각을 못했습니다..) 때문에 문제를 풀 때는 여러 edge case 를 고려하는 연습이 필요해보입니다. 코드 /** * @param {character[][]} grid * @return {number} */ var numIslands = function (grid) { const dx = [0, 0, 1, -1]; const dy = [1, -1, 0, 0]; if (.. 2021. 3. 2.

LeetCode 64 - Minimum Path Sum (Medium) 문제 LeetCode - 64번 풀이 과정 이동 방향이 고정되어 있는 상태에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다. 각 칸을 하나의 정점으로 생각하면 이동 방향이 오른쪽 혹은 아래로 고정되어 있으므로 이를 그래프로 모델링하여 다익스트라 알고리즘이나 플로이드와 같은 최단 경로 알고리즘을 사용할 수도 있을 것 같습니다. 하지만 그보다 간단하게 동적 계획법 을 활용하여 문제를 해결할 수 있습니다. 만약 dp(x, y) = (x, y)에서 출발해서 (m, n)에 도달 할 수 있는 최단경로 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(x, y) = min(dp(x+1, y), dp(x, y+1)) + cost(x, y), 이때 cost는 현재 (x, y) 에서 필요한 비용 평.. 2021. 3. 2.

이전 1 ··· 12 13 14 15 16 다음

티스토리툴바