본문 바로가기

🏃 algorithm/leetcode93

LeetCode 78 - Subsets (Medium) 문제 LeetCode - 78번 풀이 과정 멱 집합 을 구하는 문제입니다. 다양한 방법이 있겠지만 저는 비트 마스크 를 통해서 모든 부분 집합을 생성했습니다. 한가지 유의할 점은 반복문을 직접 사용하는 대신 filter 함수를 통해 subset 에 포함된 모든 비트를 찾아서 배열로 반환해줬습니다. 코드 /** * @param {number[]} nums * @return {number[][]} */ var subsets = function (nums) { let numbers = 0; nums.forEach((n) => { numbers |= 1 subset & (1 2021. 3. 3.

LeetCode 739 - Daily Temperatures (Medium) 문제 LeetCode - 739번 풀이 과정 각 날의 온도 정보가 배열로 주어질 때 각 날의 온도를 기준으로 기온이 상승하는 최초의 날을 찾는 문제입니다. 브루트 포스 를 사용해서 모든 경우를 따질 경우 O(N^2) 의 시간 복잡도로 시도해볼 수 있겠지만 입력 값의 크기 때문에 시간 초과가 발생합니다. 대신에 스택 을 사용하면 O(N) 에 이 문제를 해결할 수 있습니다. 스택 에 각 날짜의 온도를 인덱스와 함께 저장하며 만약 새로 들어오는 날짜의 온도가 top 보다 높을 경우에는 해당 날짜보다 온도가 높은 날이 남을때까지 pop 해주며 날짜 간격을 계산합니다. 만약 최종적으로 스택 이 비어있지 않다면 남아있는 온도는 모두 내림차순으로 되어 있는 것이므로 0 으로 해주면 되는 것입니다. 코드 /** * @.. 2021. 3. 3.

LeetCode 114 - Flatten Binary Tree to Linked List (Medium) 문제 LeetCode - 114번 풀이 과정 이진 트리를 연결 리스트로 변경하는 문제입니다. 별도의 메모리를 사용하면 안되기 때문에 dfs 를 응용하여 문제를 해결하였습니다. 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 연결 리스트로 변경해준 다음 왼쪽 서브트리의 꼬리 노드를 찾아 오른쪽 서브 트리 변환 결과와 연결해줍니다. 이때 루트 노드는 왼쪽 서브트리를 null 로 설정하고 오른쪽 자식을 변형 후의 왼쪽 서브트리와 연결해주면 됩니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left.. 2021. 3. 3.

LeetCode 287 - Find the Duplicate Number (Medium) 문제 LeetCode - 287번 풀이 과정 주어진 배열에서 중복된 원소를 찾는 문제입니다. 다만 시간 복잡도가 O(N^2) 보다 낮아야 하며 O(1) 의 추가적인 메모리를 사용해야한다는 제약 조건이 있습니다. 처음에는 비트 마스킹 을 이용해서 문제를 풀려고 했지만 Javascript 에서 비트 연산자를 사용할 경우 피연산자를 32비트로 취급하기 때문에 이를 넘어설 경우 overflow 가 발생했습니다. 이 문제를 해결하는 다른 방법으로는 이분 탐색 이 있습니다. 배열에서 중복된 원소는 오직 하나이며 나머지 원소들은 1 ~ n 의 숫자들 중 하나의 숫자와 매칭되기 때문에 이분 탐색 을 활용해서 중복된 원소를 찾아주기로 했습니다. 특정 기준 값 pivot 보다 같거나 작은 원소의 개수가 pivot 보다 클.. 2021. 3. 3.

LeetCode 347 - Top K Frequent Elements (Medium) 문제 LeetCode - 347번 풀이 과정 배열에서 가장 많이 등장하는 k 개의 숫자를 찾아 반환하는 문제입니다. 알고리즘의 시간 복잡도를 O(NlogN) 으로 지정해놨기 때문에 Hash Map 을 사용해서 빈도수를 저장하였습니다. 우선 배열의 각 요소를 순회하며 Map 에 빈도수를 저장하는데에는 O(N) 의 시간 복잡도가 들고, 이후 빈도수를 기준으로 Map 을 정렬하면 O(NlogN) 의 시간 복잡도를 얻게 됩니다. 마지막으로 정렬 결과 k 개의 상위 요소들을 반환해주면 됩니다. 코드 /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function (nums, k) { const nu.. 2021. 3. 3.

LeetCode 322 - Coin Change (Medium) 문제 LeetCode - 322번 풀이 과정 오랜만에 풀어보는 동적 계획법 문제입니다. dp[x] = x 원을 만들기 위한 최소 동전의 개수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[x] = for all coins, min{ dp[x - coins[i]] } 이때 i 는 i 번째 동전을 의미합니다. 코드 /** * @param {number[]} coins * @param {number} amount * @return {number} */ var coinChange = function (coins, amount) { const dp = new Array(amount + 1).fill(Infinity); // 초기값 dp[0] = 0; for (let money = 1; money 2021. 3. 3.

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

티스토리툴바