https://leetcode.com/problems/create-maximum-number/description 핵심 아이디어 숫자 붙여서 최댓값 만들기 + 순서 유지 -> Greedy 정렬 + 순서 유지 -> Decreasing Monotonic Stack 리스트의 사전 순 비교는 Python의 max(list1, list2)를 이용할 수 있다 (결과 길이) l1, l2 모든 길이 조합 경우의 수 구하기 어떤 값을 안 쓰면 결과 달라지기 때문 숫자 붙이기 - Greedy결과가 최댓값이 되는 건 모든 값을 사용하는 조건에서만 성립한다 설명 이 문제는 아래처럼 나누어서 풀어야 한다 두 리스트를 조합해서 가장 큰 결과를 만든다 Greedy하게 큰 값 선택 같은 값이면 뒤..
Problem Solving
https://leetcode.com/problems/trapping-rain-water/description/ 의 풀이 중 스택 풀이가 잘 이해되지 않아서 정리한 내용을 공유합니다 막대를 하나씩 세운다고 생각했을 때 물을 저장할 수 있는 조건을 생각해 봅시다. 다음 막대로 마지막 막대보다 높이가 같거나 작은 막대가 오면 내리막길 모양이 되어서 물을 채울 수 없습니다. (5, 4, 3, 2, 1) 마지막 막대보다 높이가 높은 막대가 오면 물을 채울 수 있는데, 이 때 이전 막대 중에서 새 막대보다 높이가 낮은 막대 위에만 물을 채울 수 있습니다. 이 때 채울 수 있는 물의 양은 막대 하나와 새 막대의 거리 * min(왼쪽 막대, 오른쪽 막대) 높이 차 로 각 막대와 새 막대의 차이 때문에 담을 수 있는 ..
https://leetcode.com/problems/longest-palindromic-substring/ Longest Palindromic Substring - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 모든 문자에 대해 two pointer를 확장해 가며 s[left] === s[right] 를 비교한다 substring 길이가 홀수인 경우, 짝수인 경우 case로 나눠서 두 번 구한다 복잡도 시간 복잡도: O(n^2) string 모든..
https://leetcode.com/problems/group-anagrams/submissions/ Group Anagrams - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 순서가 다른 문자열은 정렬하면 같은 문자열이 된다 복잡도 시간 복잡도: O(N * KlogK) 문자열 N개 * K길이 문자열 정렬 KlogK 공간 복잡도: O(N) anagrams hash map (이차원처럼 보이지만, 전체 개수는 N개이다) 설명 "문자열 배열을 받아 ..
https://leetcode.com/problems/most-common-word/ Most Common Word - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 split() 에 정규표현식 /W+/ (not word, 1 or more) 를 사용하여 알파벳만 배열 나눌 수 있다 O(N)인 Array.includes() 보다는 O(1)인 Map.has()가 시간이 적게 걸린다 복잡도 N = 단어의 개수라면, 시간 복잡도: O(N) filter ..
https://leetcode.com/problems/reorder-data-in-log-files/ Reorder Data in Log Files - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 letterLogs, digitLogs 두 배열로 나눈 뒤 합친다 js string 비교는 String.localeCompare()로 할 수 있다 복잡도 시간 복잡도: O(N^2*logN) sort() NlogN * slice() N 공간 복잡도: O(..
https://leetcode.com/problems/reverse-string/ Reverse String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 js에 Array.reverse() 가 있으니 그걸 쓰거나... left, right two pointer로 양쪽에서 반복하며 swap하면 배열이 뒤집어진다 js에서 swap할 때는 destructing asssignment [a,b] = [b,a] 를 활용할 수 있다 복잡도 시간 복잡도: ..
https://leetcode.com/problems/valid-palindrome/ Valid Palindrome - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 s === s.split("").reverse().join("") 소문자 일괄 변환은 .toLowerCase()로 하고 알파벳 숫자 아닌 문자 거르기는 정규표현식 /[^a-z0-9]/g 를 사용한다 python, c++ 등 deque 자료구조를 지원한다면 deque로 풀 수 있다 맨 ..