문제링크https://leetcode.com/problems/intersection-of-two-arrays-ii/description/문제풀이해시테이블을 이용한 풀이 -> Time complexity O(n)/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */var intersect = function (nums1, nums2) { const map = new Map(); const answer = []; for (const n of nums1) { map.set(n, (map.get(n) || 0) + 1); } for (const n of nums2) { if..

🧩문제링크https://leetcode.com/problems/maximum-product-difference-between-two-pairs/🔨문제풀이이 문제는 처음에 sort로 정렬해서 1,2번째로 가장 큰수, 1,2번째로 가장 작은 수들을 바로 이용하는 방식으로 풀었는데 시작복잡도를 더 최적화 하는방법이 있었고 그 방법이 아래 방법이다. 단순히 nums의 모든 원소들을 sorting 하는방식은 시간복잡도나 O(nlogn)이고 아래 풀이의 시간복잡도는 O(n)이다.  ( 참고로 js에서 사용하는 sort 함수의 시간복잡도는 O(nlogn)이다. ) /** * second try * time complexity O(nlogn) * @param {number[]} nums * @return {numb..

문제링크https://leetcode.com/problems/number-of-equivalent-domino-pairs/description/풀이처음 푼 방식이다. 어렵지 않게 풀 수 있었으며 시작 복잡도는 O(n) 이다. 지금 생각해보면 굳이 arr.sort()를 통해 정렬한뒤 join으로 새로운 배열을 생성한 뒤 다시 연산을 할게 아니고 처음 arr를 순회하면서 모든 연산을 처리할 수 있었다. 이런 개선점들이 보여 한번 더 정리를 했다. (하단 2번째 코드 확인)/** * @param {number[][]} dominoes * @return {number} */var numEquivDominoPairs = function (dominoes) { dominoes = dominoes.map((ar..

📌문제링크https://leetcode.com/problems/buddy-strings/🔨문제풀이이 문제는 s, goal 이 서로 완전히 동일한 문자일 때, 문자열 길이가 다를때, 문자중에 2개만 다를때를 분기처리하여 풀면 된다. 결국 경우를 파악할 수 있어야 한다. 조금만 생각하면 쉽게 풀 수 있다. 시간복잡도는 O(n)이다. 완전히 동일한 문자열일 때는 s 문자중 중복되는 문자가 있으면 해당 문자끼리 순서를 바꿔도 동일한 문자열이 되는데 이를 확인하기 위해 나는 Set() 객체를 썻다. Set 객체는 얼핏보면 시간 복잡도가 O(n^2) 처럼 보일 수 있는데 Set객체는 내부적으로 Hash Table을 사용하여 실제론 O(n) 이다. /** * @param {string} s * @param {st..

문제링크https://leetcode.com/problems/minimum-index-of-a-valid-split/description/문제풀이dominant한 수는 주어진 배열에서 정확히 1개라고 전제가 되어 있다. 배열에서 특정 수가 반보다 많이 등장한다는 애기이다. 예를들어서 [1,2,3,2] 이런 배열은 dominant수가 없기 때문에 주어질 수 없다는 애기이다.  주어진 배열을 split 하여 왼쪽, 오른쪽 2개의 배열로 나누었을 때 각 배열의 dominant한 수가 같은 split point를 알아야 된다.주어진 배열에서 dominant한 수는 한개이므로  애초에 주어진 배열을 2개로 나누고 각 배열의 dominant한 수가 같을 때 그 수는 원래 배열의 dominant 수일 수 밖에 없다...

📌링크https://leetcode.com/problems/minimum-operations-to-halve-array-sum/description/🔨풀이이 문제의 조건을 보면 단순히 정렬을 이용해서 풀면 시간초과가 날 것이라고 생각되어 우선순위 큐를 이용하여 연산횟수를 최적화 하였다. 우선순위 큐를 구현하기 위해 힙(완전이진 트리) 자료구조를 이용하였고 우선순위 큐에서 가장 큰 값을 반으로 나누면서 계산횟수를 카운팅 하여 문제를 풀 수 있었다. 해당 문제의 시간복잡도는 O( n log n ) 이다. ( 시간복잡도 관례대로 log의 밑은 생략 )  /** * @param {number[]} nums * @return {number} */var halveArray = function (nums) { ..

문제https://leetcode.com/problems/check-if-n-and-its-double-exist/풀이쉽게 풀 수 있다. 시간 복잡도는 O(n^2) 이다./** * @param {number[]} arr * @return {boolean} */var checkIfExist = function(arr) { for(let i =0; i

➕문제https://leetcode.com/problems/number-of-lines-to-write-string/description/➕풀이character의 코드를 이용하면 쉽게 풀 수 있다. 시간 복자도는 O(n) 이다./** * @param {number[]} widths * @param {string} s * @return {number[]} */var numberOfLines = function (widths, s) { let base = "a".charCodeAt(0); let line = 1, pixels = 0; for (let i = 0; i

📌LRU 알고리즘LRU(Least Recently Used) 알고리즘은 가장 오랫동안 사용되지 않은 데이터를 제거하는 전략이다. 캐시 교체 방식으로 많이 쓰인다. 해당 알고리즘은 hash 와 double linked list 를 이용하여 구현할 수 있다. 📌실제로 구현해봤다.자바스크립트로 구현해봤다. hash table은 Map 객체를 이용했으며 Map에는 각 key에 대응되는 node가 저장되어 있다. ( 각 노드의 prev, next 는 이전,다음 노드를 카리킨다 ) // LRU cache 교체 알고리즘 구현 (has table + double linked list이용 )class Node { constructor(key, value) { this.key = key; ..

📌문제링크https://leetcode.com/problems/convert-1d-array-into-2d-array/description/📌풀이시간 복잡도는 O(n) 으로 큰 무리 없이 풀 수 있었다.// 시간 복잡도 O(n)/** * @param {number[]} original * @param {number} m * @param {number} n * @return {number[][]} */var construct2DArray = function (original, m, n) { if (m * n !== original.length) { return []; } let answer = []; for (let i = 0; i