본문 바로가기

알고리즘/리트코드

 (18)
LeetCode 787. Cheapest Flights Within K Stops 먼저 Map을 사용하여 인접리스트를 만들어줍니다. 인접리스트를 잘 채워준 이후에 큐를 선언하고 출발지부터 넣어줍니다. while 문을 돌면서 queue를 거리순으로 정렬하고 가장 거리가 가까운 것 부터 방문해나갑니다. 방문했던 곳에서는 방문했던 곳에서부터 더 방문할 수 있는 수를 확인해서 현재 방문할 수 있는 개수 - 1 보다 더 많이 방문할 수 있다면 continue를 해줍니다. 모든 간선을 사용하거나 도착지에 도착하면 while 문이 종료됩니다. const findCheapestPrice = function(_, flights, src, dst, K) { const adjacencyList = new Map(); for(const [start, end, cost] of flights) { if(adj..
LeetCode 93. Restore IP Addresses IP 주소로 가능한 모든 경우의 수를 구해야 한다. -> 백트래킹 일단 길이가 4보다 작거나 12보다 크면 IP 주소를 만들수조차 없으므로 빈 배열을 반환하게 했다. 또한 조건에서 string에 속할 수 있는 것은 숫자뿐이므로 문자열 -> 숫자 변환은 parseInt(x) 또는 Number(x)를 이용한다. backtracking 함수에서 탈출조건은 배열의 현재 길이가 4일 때 join으로 합쳐서 정답 배열에 푸쉬한 후 탈출하기로 했다. 또한 탈출조건으로 현재 배열이 3개이고 남은 문자열의 길이가 3이상이라면 적절한 IP 주소를 만들 수 없으므로 제거하는 베이스케이스를 추가했다. 그 후에는 전형적인 백트래킹을 활용했다. 풀이는 아래와 같다. const restoreIpAddresses = (s) => {..
Leetcode 45. Jump Game II a처음에는 재귀를 이용한 완전 탐색으로 접근했다. /** * @param {number[]} nums * @return {number} */ const jump = function(nums) { const endIndex = nums.length - 1 let ans = Infinity function travel(position, count) { if (position > endIndex) { return } if (position === endIndex) { ans = Math.min(ans, count) return } const jumpRange = nums[position] for (let i = 1; i = nums.length - 1) return 0 if (memo[idx]) return ..
43. Multiply Strings 문제를 읽고 생각을 별로 안하고 답을 내면 아래와 같은 답을 제출한다. const multiply = function(num1, num2) { return String(parseInt(num1) * parseInt(num2)) }; 이렇게 내면 무조건 틀리는데 이유는 정말 큰 수를 곱하면 overflow가 나기 때문이다. 따라서 배열에 저장하면서 "잘" 곱해줘야한다. 잘 곱해준다는 의미는 아래와 같이 배열에 저장하면서 곱하는 것을 의미한다. const multiply = function(num1, num2) { if (num1 === "0" || num2 === "0") return "0" // 0이면 무조건 0리턴 const n = num1.length, m = num2.length // 배열 길이 저..
139. Word Break 두가지 컨셉으로 접근할 수 있다. 첫째. BFS 인덱스 0부터 시작해서 특정 단어의 마지막 인덱스보다 1큰값을 큐에 넣어주면서 bfs진행 const wordBreak = function(s, wordDict) { const set = new Set(wordDict); const visited = new Set() const q = [0] while (q.length) { const start = q.shift() if (!visited.has(start)) { for (let end = start + 1; end { if (wordDict == null || wordDict.length === 0) return false; const set = new Set(wordDict); const dp = Arr..
54. Spiral Matrix 유명한 돌아가는 문제이다. (소용돌이 문제 같은 느낌) 이문제는 단순하게 노동하는 방법도 존재하지만 엄청 이쁜 풀이도 존재한다. 우선 이쁜 풀이를 보자. const spiralOrder = function(matrix) { const res = [] while(matrix.length){ const first = matrix.shift() res.push(...first) for(const m of matrix){ let val = m.pop() if(val) res.push(val) m.reverse() } matrix.reverse() } return res };첫라인은 그대로 출력하고 배열에서 없앤다. 두번째 라인부터 마지막 라인까지 마지막꺼 출력하고 뒤집어 놓는다. 그다음에 전체 매트릭스를 뒤집는..
22. Generate Parentheses 모든 쌍을 다 찾아야 하므로, dfs를 진행했다. 여는괄호, 닫는 괄호가 둘다 0이 되었을 때, 배열에 푸쉬를 해주었고, 오른쪽 괄호의 개수가 더 작다면 무조건 리턴조건, 왼쪽 괄호의 개수가 0보다 작다면 무조건 리턴 조건에 포함된다. 따라서 풀이는 아래와 같다. const generateParenthesis = function(n) { let res = []; const dfs = (str, left, right) => { if(left === 0 && right === 0) { res.push(str); return; } if(right < left || left < 0) return dfs(str+"(", left - 1, right) dfs(str+")", left, right - 1) } dfs..
33. Search in Rotated Sorted Array 문제에서 O(logn)으로 풀어야 한다고 명시가 되어있다. 이 문제에서 중요한 부분은 두 배열로 나눴을 때 둘중 하나는 무조건 정렬된 상태라는 것이다. 그렇게 생각하면 왼쪽이 정렬되어있다면, 오른쪽은 정렬되지 않았을 것이고, 반대의 경우도 마찬가지이다. 왼쪽이 정렬된 상태일 경우에, 타겟이 그 정렬된 숫자들 사이에 있는 값이라면, right을 mid - 1 로 바꿔주고, 만약 타겟이 그 숫자들 사이에 있지 않다면, 그 left를 mid+1로 바꿔주면서 탐색한다. const search = function(nums, target) { let left = 0; let right = nums.length - 1; while (left

티스토리툴바