👨💻📱✍️🎢314 LeetCode 704 - Binary Search (Easy) 💡 문제 LeetCode - 704번 🎯 풀이 과정 정렬된 배열에서 특정 target 의 index 를 반환하는 문제입니다. 이분 탐색 을 이용하면 쉽게 해결할 수 있습니다. 👨💻 코드 /** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { let head = 0 let tail = nums.length - 1 let answer = -1 while (head target) { tail = mid - 1 } else { answer = mid break } } return answer }; 2023. 5. 14. LeetCode 438 - Find All Anagrams in a String (Medium) 💡 문제 LeetCode - 438번 🎯 풀이 과정 문자열 s 에서 p 의 아나그램을 만족하는 모든 부분 문자열의 위치를 찾는 문제입니다. 문자열의 길이를 고려해서 최적의 시간 복잡도로 문제를 해결해야하는데, sliding window 를 활용하면 O(n) 에 모든 위치에서 아나그램을 판단할 수 있습니다. 먼저 p 를 구성하는 문자 빈도수 해시맵을 생성합니다. 이후 두 개의 포인터 left 와 right , 아나그램 구성에 필요한 문자 개수의 합을 위한 count 를 정의합니다. count 가 0이 되면 모든 문자들이 필요한 빈도수만큼 발견되었다는 것을 의미합니다. window 의 크기는 곧 p 의 길이와 같기 때문에 left 와 right 간의 간격이 window size 에 도달하면 left 를 하나.. 2023. 5. 14. LeetCode 42 - Trapping Rain Water (Hard) 💡 문제 LeetCode - 42번 🎯 풀이 과정 웅덩이를 찾기 위해서는 단조감소 구간을 알아야합니다. O(n) 에 이를 알 수 있는 방법이 무엇일까요? 이를 위해 monotonic stack을 활용할 수 있습니다. height 의 인덱스를 i 라고 하겠습니다. (a) height[i] 가 stack top 보다 작다면 그냥 push 합니다. (b) stack top 값보다 크거나 같다면 push 하기전에 stack 에서 height[i] 보다 작거나 같은 값을 가지는 요소들을 모두 pop 합니다. 물 웅덩이의 크기를 알려면 높이 * 너비 를 알아야합니다. 너비는 index 값으로 쉽게 알 수 있고, 높이는 다음과 같이 구할 수 있습니다. min(height[stack[top-1]], height[i]).. 2023. 4. 30. GitHub Actions 를 활용한 release bot 만들기 이번에 사내에서 메일 템플릿을 관리하는 프로젝트의 배포 방식을 변경하는 업무를 맡아 진행하며 Github Action (이하 GHA)을 다뤄볼 기회가 생겼습니다. GHA로 PR에서 특정 comment 를 남기면, 변경사항을 배포해주는 자동화 프로세스를 만들고 싶었는데 GHA 사용이 처음이라 꽤나 많은 삽질을 해서 비슷한 기능을 구현하고 싶은 분들을 위해 기록을 남기려고합니다. 📌 PR comment echo 테스트하기 우선 PR에서 특정 명령어를 담은 댓글을 남기면, 이를 감지하는 workflow 를 작성해보겠습니다. release 라는 comment 를 남기면 workflow 가 해당 PR 에 댓글로 응답해주는 workflow 를 작성합니다. comment 추가는 issue_comment event 를.. 2023. 4. 24. LeetCode 238 - Product of Array Except Self (Medium) 💡 문제 LeetCode - 238번 🎯 풀이 과정 배열 num 에서 i 번째 요소만 제외한 나머지 요소들의 곱을 i 번째 인덱스에 할당한 결과를 반환해야합니다. 이때 O(n) 의 시간복잡도로 수행되어야하고, 나누기 연산을 사용하면 안되는 제약조건이 있습니다. 이를 위해서 i 번째 요소를 제외한 나머지 요소들의 곱을 다음과 같이 나눠서 생각할 수 있습니다. answer[i] = num[0...i-1] * num[i+1...] 부분합 알고리즘을 차용하면, 위에서 필요한 구간곱을 미리 계산해놓을 수 있습니다. 한 배열에는 왼쪽에서부터 누적한 곱을 저장하고, 다른 배열에는 오른쪽에서부터 누적한 곱을 저장합니다. 그러면 위 식은 다음과 같이 바꿔서 계산할 수 있습니다. answer[i] = prefixLeft[.. 2023. 4. 24. LeetCode 2390 - Removing Stars From a String (Medium) 💡 문제 LeetCode - 2390번 🎯 풀이 과정 별표 (*)를 포함한 문자열 s 에서 다음 규칙에 따라 모든 별표가 제거된 문자열을 반환하는 문제입니다. 별표가 있을 경우 해당 별표보다 앞쪽에 위치한 가장 가까운 문자를 제거합니다. 스택을 활용하면 간단하게 해결이 가능한데, 입력으로 주어지는 문자열의 길이가 크기 때문에 (10^5) 문자열을 순회하며 자료구조에 하나씩 push, pop 하기 보다는 다른 방법을 사용했습니다. 규칙을 활용해서 문자열의 가장 뒤쪽 부터 순회를 해줍니다. 이때 * 를 만나면 answer 에 추가하지 않고 별표의 개수를 계속 세어주다가 일반 알파벳을 발견하면 저장해놨던 별표 개수를 하나씩 줄이고, 만약 저장되어있는 별표 개수가 없다면 그 문자를 answer 에 추가해줍니다... 2023. 4. 24. 이전 1 2 3 4 5 6 7 8 ··· 53 다음
