본문 바로가기

leetcode87

LeetCode 35 - Search Insert Position (Easy) 💡 문제 LeetCode -35번 🎯 풀이 과정 target 이 배열에 존재할 경우 해당 요소의 index를, 만약 존재하지 않을 경우 target 이 위치해야할 index 를 반환하는 함수를 구현하는 문제입니다. 문제 조건에서 따라 정렬된 배열에서 이분 탐색 을 사용하면 O(logn) 에 해결할 수 있습니다. 👨‍💻 코드 /** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { let answer = null function findItem(head, tail) { if (head >= tail) { if (nums[head] === target).. 2023. 2. 20.
LeetCode 169 - Majority Element (Easy) 최근 몇달동안 LeetCode 문제풀이를 못했는데, 올해에는 재미와 성취감을 위해 시간 날때마다 짬내서 간단한 문제를 하나씩 다시 풀어보려고합니다. 😄 💡 문제 LeetCode - 169번 🎯 풀이 과정 n 크기의 배열이 주어질 때, 과반수 이상의 요소를 찾는 문제입니다. 해시맵을 이용해서 구현할수도 있지만 좀 더 최적화된 방법으로 해결할 수도 있습니다. 요구조건에 의해 과반수를 차지하는 요소가 반드시 존재한다는 것이 보장되기 때문에 보이어-무어 과반수 투표 알고리즘 을 활용하면 O(n) 의 시간복잡도와 O(1) 의 공간 복잡도를 가지는 풀이를 만들 수 있습니다. 이 알고리즘을 간단히 풀어보자면, 길이 n 을 가지는 배열 A 에서 과반수를 차지하는 요소 a가 [n/2 + 1] 개 있을 경우에 나머지 요소.. 2023. 2. 5.
LeetCode 733 - Flood Fill (Easy) 💡 문제 LeetCode - 733번 🎯 풀이 과정 BFS 를 이용해서 도달 가능한 모든 지점을 확인하는 문제입니다. 여기서 visit 이라는 2차원 배열을 유지하며 중복 방문을 검사함과 동시에 도달 가능한 위치를 기록합니다. 👨‍💻 코드 /** * @param {number[][]} image * @param {number} sr * @param {number} sc * @param {number} newColor * @return {number[][]} */ var floodFill = function (image, sr, sc, newColor) { const dr = [0, 0, 1, -1] const dc = [1, -1, 0, 0] const [ROW, COL] = [image.length, .. 2022. 3. 7.
LeetCode 229 - Majority Element II (Medium) 💡 문제 LeetCode - 229번 🎯 풀이 과정 배열에 담긴 숫자들 중에서 일정 기준값 이상의 숫자들을 찾아서 반환하는 문제입니다. 배열에 담길 수 있는 숫자의 범위가 크기 때문에 해싱을 이용해서 숫자들의 개수를 세어줍니다. 여기서는 객체 대신에 읽고 쓰는 성능이 더 뛰어난 Map 을 사용했습니다. 👨‍💻 코드 var majorityElement = function (nums) { const numCount = new Map(); const pivot = nums.length / 3; for (const num of nums) { if (numCount.has(num)) { const oldVal = numCount.get(num); numCount.set(num, oldVal + 1); } else.. 2022. 2. 22.
LeetCode 300 - Longest Increasing Subsequence (Medium) 문제 LeetCode - 300번 풀이 과정 가장 긴 부분수열을 구하는 LIS 문제입니다. 동적 계획법 을 이용해서 문제를 해결할 수도 있지만 이분 탐색 을 이용하면 Nlog(N) 의 시간 복잡도로 해결할 수 있습니다. 코드 /** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function (nums) { const memo = []; for (const num of nums) { if (memo.length === 0) { memo.push(num); continue; } if (memo.length > 0 && memo[memo.length - 1] < num) { memo.push(num); } else { const idx .. 2021. 6. 14.
LeetCode 36 - Valid Sudoku (Medium) 문제 LeetCode - 36번 풀이 과정 스도쿠 를 구현하는 문제입니다. 대신 모든 로직을 구현하는 것은 아니고 채워진 숫자들에 대해서 스도쿠 조건을 만족하는지 판단하는 문제입니다. 먼저 3x3 크기의 서브 박스들에서 19 사이의 숫자들 중 중복이 존재하는지 검사합니다. 이후 각 행과 열을 순회하며 마찬가지로 19 사이의 숫자 중복성을 검사합니다. 코드 /** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function (board) { const isSubboxRepetition = checkSubboxes(board); if (!isSubboxRepetition) { return false; } for (let .. 2021. 4. 13.

티스토리툴바