Apes Together Strong.

https://leetcode.com/problems/longest-consecutive-sequence/description/ 주어진 숫자 배열에서 연속된 증가수의 최대 길이를 찾아라. 이때 O(n)의 TC를 만족하는 알고리즘을 작성하라. 값에 대한 조회가 O(1)에 가능해야 하므로, hash를 사용해야 한다. 또한 전체적으로 O(N)에 로직이 작성되어야 한다. 따라서 2중 for loop를 피한다.  증가되는 수의 시작 지점을 조회하여 연속된 만큼 카운팅 한다. 시작지점 조회 - O(n)각 지점에 대한 연속된 수 카운팅 O(x) 최적 O(n)최악 O(n + x)  음 다소 애매. 더보기int longestConsecutive(vector& nums) { if(nums.size() sBuff; ..

https://leetcode.com/problems/valid-sudoku/description/  아래와 같은 sudoku 룰 이 있을 때, 이 rule에 대해 주어진 입력이 유효한지 판단하라.   2차원 array에 대한 coding ability test.  별다른 함정은 없는 문제.  코드 더보기bool isValidSudoku(vector>& board) { const int W = 9; const int H = 9; set sBuff; // check row. for (auto x = 0; x   결과.

https://leetcode.com/problems/product-of-array-except-self/description/  정수 배열이 주어 질 때, 자신을 제외한 곱을 구하는 알고리즘을 작성하라. 이때 O(n)의 TC에 추가 메모리를 사용하지 말라. 이때 반환할 버퍼는 추가 메모리로 간주하지 않는다.  자주 나오는 패턴의 문제. 제한이 없을 때 매우 간단한 문제.  O(n)의 TC 제한이 있으므로, 2중 loop는 허용되지 않는다. O(1)의 space complexity 만을 가져야 하므로, 반환할 버퍼에 임시 데이터를 쓴다. 더보기vector productExceptSelf(vector& nums) { vector vRet; vRet.resize(nums.size()..

https://neetcode.io/problems/string-encode-and-decode  NeetCode neetcode.io 주어진 string을 조각으로 분해 한 후, 다시 합치는 로직 즉, encode, decode 함수를 만들어라.  역시 여러가지 다양한 방법이 있을 수 있겠으나, 나누는 문자 등과 구분을 위하여, 길이+string 꼴로 변환할 필요가 있다는 것이다.  이것에 유의해서 만들면 큰 어려움은 없을 것.  코드 더보기string encode(vector& strs) { string ret = ""; for (auto k = 0; k decode(string s) { vector vRet; string sCur = ""; int cnt = -1; ..

https://leetcode.com/problems/top-k-frequent-elements/description/  숫자 배열이 주어질 때, k 번째로 많이 등장하는 원소까지 찾아라.  여러 가지 방법이 있을 수 있다. frequency buffer를 만들고 frequency 수로 정렬한다. map을 이용해서 정렬할 수도 있고, priority queue를 이용할 수도 있다.  하지만, follow up에서 보다시피, O(nxlog(n)) 을 넘지 말라고 명시하고 있다.따라서 조금 더 생각해 볼 여지가 있다.  일단 sort 나 일반 map 은 정렬에 의존하므로, n x log(n) 이다. 이것은 기준에 부합하지 않는다. 다음으로 priority queue를 보자. insert 시 O(n), pop..

https://leetcode.com/problems/group-anagrams/description/ 문장들의 배열이 주어질 때, anagram이 같은 것들끼리 묶어서 출력하라.  우선 이 문제를 풀때는 frequency buff를 사용한다는 생각에 미치는 것이 일반적이다. 하지만 조금 더 최적화를 위해서를 입력된 문자를 정렬하면 anagram이 같은 문자는 같은 문자로 정리된다는 생각에 까지 이르러야 한다.  코드 더보기vector> groupAnagrams(vector& strs) { map> mBuff; for (auto k = 0; k { k }; else mBuff[cur].push_back(k); } vector> vRet; for ..

https://leetcode.com/problems/two-sum  숫자 배열이 주어질 때, 두 수의 합이 target이 되는 두개의 index를 반환하라.   map를 이용해서 간단히 푼다. 더보기vector twoSum(vector& nums, int target) { map mBuff; for (auto q = 0; q { itRet->second, q }; } int val = target - nums[q]; mBuff[val] = q; } return vector{};} 결과.

https://leetcode.com/problems/valid-anagram/description/ 주어진 두 문자열이 anagram 인지 판단하라.  Frequencey buffer를 쓰면 간단한 문제.더보기bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; map mBuff; for (auto q = 0; q   결과.

https://leetcode.com/problems/contains-duplicate/https://neetcode.io/roadmap  주어진 숫자 배열에서 중복된 수를 찾아라.  ; 딱히 함정이 없는, 진짜 easy 난이도의 문제.  bool ArraysHashing::containsDuplicate(vector& nums){ set sBuff; for (auto q = 0; q  결과.  unordered_set 등을 사용하면 조금더 빨라질 여지는 있을 듯.

https://leetcode.com/problems/clone-graph/description Q. 주어진 그래프를 deep copy 하여 반환하라.   Solution 기존 graph를 순회하며 모든 node의 포인터를 중복되지 않게 우선 저장한다.  이후 각 노드의 neighbors만큼 새로운 node를 만든다.  새로운 노드를 순회하며, 각자의 neighbors에 새로운 node를 link한다.   코드 더보기 Node* cloneGraph(Node* node) { if(node == nullptr) return node; // adding nodes into map. set setNodes; queue qBuff; qBuff.push(node); while(qBu..