Apes Together Strong.

https://leetcode.com/problems/add-two-numbers/description A. 두개의 단방향 linked list가 주어질때 각 자리수는 숫자의 digit 자리수 값을 의미한다. 이때 주어진 두개의 리스트 값을 digit에 맞게 계산하여 다시 리스트로 반환하라. Solution. 리스트가 단방향이다. 뒤집어야 하나, 생각해 봤지만, 그럴 필요 없이, 각 자리수 대로 합해주고 출력한다. 더보기 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { ListNode prev = null; ListNode head = null; bool bHasOverflow = false; while(l1!=null || l2!=null || b..

https://leetcode.com/problems/top-k-frequent-elements/description Q. 주어진 숫자배열 nums에서 k번째까지 많이 나오는 수의 목록를 찾아 반환하라. Solution 먼저 출현 빈도를 알아야 하니, frequency buff를 만든다. 다음으로, 이 출현 빈도만큼, map 이나 heap에 넣어 정렬되도록 한다. 그리고 k 만큼 해당하는 수를 찾아 리스트에 넣어 반환한다. 논리대로 코드를 만든다 . 더보기 vector topKFrequent(vector& nums, int k) { unordered_map mapBuff; for(int k = 0; k < nums.size(); ++k) { mapBuff[ nums[k] ]++; } map mapOrde..

Q. 주어진 값들의 중앙값을 반환하는 클래스를 만들어라. 이때 중앙값은, 값들의 수가 홀수일때는 가운데 존재하는 값, 짝수일때는 가운데 양 옆 두수의 평균을 말한다. Solution. 입력된 수들을 정렬 했을 때, 가운데 지점을 찾아야 한다. 따라서 솔루션 1. 값을 리스트에 계속 추가하고, 가운데 값을 구할 시 정렬하고 중간값을 찾는다. -> 정렬에 O(N x LogN)이 매번 소모된다. 비 효율적이다. 솔루션 2. map 등의 구조를 사용하여 넣을 시 정렬한다.O(logN) -> 중간값을 찾을 때 위치 순회하는데, O(N/2) 이 소모된다. 나쁘진 않아 보이지만, 더 효율적인 방법을 생각해 본다. 솔루션 3. 두개의 priority queue를 활용해 본다. 중간값보다 작은 녀석들은 max heap ..

https://leetcode.com/problems/longest-consecutive-sequence/description  Q. 정렬되지 않은 정수 배열 nums가 주어질 때, 연속된 숫자들의 최대 길이를 구하라.  이때 Time Complexity 가 O(N) 이 되도록 알고리즘을 작성하라.   Solution.  TC가 O(N)이 되야 하므로, 정렬은 쓰면 안되는 것이다.  map이나 set에 넣는 것도 넣을 때 log(N), 이것을 모든 원소들에 대해 수행 주고 찾고 해야 하므로, 결국 Nxlog(N)이 걸리므로, 역시 쓰면 안되는 것이다.   그렇다면 hash 정도 쓰면 되는 것인데, c++ 에서는 unordered_map, unordered_set 을 쓰면 배열처럼 O(1)에 데이터 접근이..

https://leetcode.com/problems/group-anagrams/description Q. 문자열이 주어질 때, 이 문자들을 같은 anagram 단어들의 그룹으로 묶어서 출력하라. anagram 은 각 캐릭터의 위치 변경으로 구성할 수 있는 다른 단어들을 의미한다. 따라서 각 캐릭터들은 모든 단어에 1회씩 등장한다. Solution. 각 string을 대표할 수 있는 하나의 key를 만들고 해당 key에 매칭되는 string끼리 묶으면 될 것이다. 단어들은 같은 캐릭터들의 조합들의 모음이므로, 정렬하면 같은 캐릭터 순서가 나올 것이다. 이를 이용해 map을 만들어 단어를 묶는다. 더보기 vector groupAnagrams(vector& strs) { unordered_map group;..

https://leetcode.com/problems/two-sum/description Q. 주어진 정수 배열에서 두 합이 target이 되는 두 index를 반환하라. Solution. 많이 나오는 패턴의 문제. 값을 키로 하고 위치를 바로 접근 가능하도록 해시화 하는 것이 문제 풀이의 핵심. 문제 자체에 제한이 있으므로, 중복키는 마지막 위치로 대처해도 로직은 정상 작동. 더보기 vector twoSum(vector& nums, int target) { unordered_map mapPos; for(int q = 0; q < nums.size(); ++q) mapPos[ nums[q] ] = q; vector vRet; for(int q = 0; q < nums.size(); ++q) { int d..

https://leetcode.com/problems/partition-labels/description Q. 문자열 s 가 입력으로 있을 때, 한 파티션에만 해당 문자가 존재하도록 최대한 많은 파티션을 구성하고, 그 각 길이를 반환해라. Solution. 문제 해독에 우선 정확성을 기해야 한다. 위 예제에서 보듯이 전체 문장안에서 파티션을 나누되, 파티션 안에는 그 안에만 존재하는 문자들로 이루어져 있어야 한다. 크게 나누면 더 쉬운 확률로 가능해 지지만, 최대한 많이 나눠서 반환하라는 것이 문제이다. 문제를 이해했으니, 최적해를 찾는 로직을 구상해 본다. s의 첫번째 char, a가 등장하는 마지막 위치를 찾는다. s의 두번째 char, b 가 등장하는 마지막 위치를 찾는다. 찾아보니, a의 마지막 ..

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/ Q. stock의 가격 prices 배열이 주어진다. 하루에 하나씩 팔거나 혹은 살 수 있고, 한번에 하나의 stock만들 가질 수 있을 때, 최대의 수익을 구하라. Solution. 우선 매일(모든 index)위치에서 팔거나 혹은 사거나 아니면 아무것도 안하거나의 세개의 action이 가능하다. 다만, 이전에 샀으면 이번에는 팔기만 가능하며, 안샀으면 사기만 가능하다. 따라서 이전 조건에 따라 각 2가지만 가능하다. 이대로 DP로 접근 해 본다. DP의 핵심은 이전 누적값에 영향을 받지 않게, 특정 위치에서 독립적으로 끝까지 계산한 결과를 갖도록 로직을 만들어야 하..

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description Q. 주가의 각 날에 해당하는 가격 prices 배열이 주어진다. 이때 단, 하루 사서 다른 날 판다면, 이 최대 이익을 구하라. Solution. 고전이지만 좋은 문제다. 2 중 for loop를 쓰면 간단하겠지만, 그 답을 원하는 것은 아니다. trick 같은 사고의 전환이 다소 필요하다. loop을 돌면서 최소 가격을 갱신한다. 현재 가격에 이 최소 가격을 제하여 판매가격을 만들고 이 최대값을 저장한다. 이 최대값이 우리가 원하는 값이 된다. 최소값은 이 값을 근거로 추후 값에 차감을 해야만 의미가 있는데, 이 방식은 최소값과 그 차이값을 매번 하므로, 이에 부합한다...

Q. nums의 계단이 주어질 때, 현재 위치의 nums 값이 해당 위치에서 점프 할 수 있는 계단 수이다. 이때 마지막 계단에 도달 가능한지 여부를 반환하라. Solution. 일단 기본 로직 자체는 큰 복잡함이 없다. 특정 위치에서 가능한 모든 위치를 뛰어 본다. 그리고 끝에 도달하면 성공 실패 여부를 기록하고, 캐싱한다. 처음으로 되돌아와 계속 확인시 이 캐시를 확인한다. 기본적인 dp 문제다. 더보기 bool help(vector& vCache, vector& nums, int idx) { if(idx == nums.size()-1) return true; if(vCache[idx] >= 0) return vCache[idx]==1; for(int q = 1; q = nums.size()) bre..