Apes Together Strong.

https://leetcode.com/problems/trapping-rain-water/description Q. 각 배열값이 기둥의 높이를 의미하는 배열 height 가 주어질 때, 해당 기둥들에 물을 가둔다면, 가둘 수 있는 물의 양을 계산하라.   Solution.  생각해 볼 점이 있는 문제다.  여러가지 방법이 있을 수 있지만, 최적으로 푸는 방법을 찾아 본다.   우선 가둬진 물의 양을 알아내려면 해당 위치 기준으로 이 위치를 가두는 양쪽 기둥의 높이를 알아야 한다.  그리고 이 양쪽 기둥 중, 낮은 기둥과 현재 위치의 높이가 해당 위치의 물의 양이 된다.   예를 들어 2 index 위치에서의 양쪽 기둥은, 1, 3 index 가 되며, 높이는 각각 (1, 2) 이다.  낮은 높이는 1 이..

https://leetcode.com/problems/3sum/description Q. 숫자배열 nums가 주어질 때, 세 수가 다르면서 그 합이 0 이 되는 수들의 집합을 구하라. 이때 결과값이 중복되어서는 안된다. Solution. 숫자 두개의 합에 대해서 구할때는 hash 를 쓰면된다. 하지만, 셋은 조금 접근법이 다르다. 두개에 대해서는 하나를 찾으면 나머지를 바로 알 수 있지만, 세개는 남은 두개를 다시 찾기 쉬운 형태로 만들어 놓아야 한다. 여기서는 nums를 정렬시켜 놓아 이 형태로 만든다. 즉, 첫 수는 loop로 정하고, 나머지 두 수는 남은 수 중 가장 큰 수와 작은 수를 비교 한다. 이때 두 수의 합이 첫 수보다 크다면, 큰수 쪽을 작은 쪽으로 이동 시킨다. 작다면, 작은 수 쪽은 ..

https://leetcode.com/problems/min-stack/description Q. Min 값을 언제나 반환할 수 있는 stack class를 설계하라. 이때 모든 함수는 O(1)으로 수행되어야 한다. Solution. 우선 기본 stack 작동을 해야 하므로, 내부적으로 그냥 stack을 하나 가진다. 그리고 min 값을 위한 자료구조를 하나 더 두는데, 역시 stack으로 둔다. 이 min stack이 비었거나, top 보다 같거나 작으면 이 stack에 값을 채운다. 즉, 적은 값들이 계속 top으로 가게 끔 값을 채운다. => 여기서 큰 값들은 관심이 없으므로, min stack에 저장할 필요가 없다. getMin 할 때, 이 min stack에서 하나씩 peek해서 주면 된다. 다..

https://leetcode.com/problems/sliding-window-maximum/description Q. nums 배열과 함께 정수 k 가 주어진다. 정수 k 길이 만큼의 window가 있고 이것이 우측 끝까지 이동 할때, 각 window의 최대 값을 찾아라. Solution. window 사이의 수를 확인하며 최대값을 기억한다. 그렇게 일단 첫번째 window의 최대값은 얻는다. window를 우측으로 이동 시킨다. 값을 추가 했지만, 최대값보단 작다. 그리고 k간격을 유지하기 위해 left를 당겨야 하는데, 이때 위치 정보로 그냥 지우게 되면 다음 최대값을 다시 window loop로 찾아야 한다. (지우는 값이 구간 최대 값이라면, 다음 최대값을 어떻게 찾는가? - 이대로라면 다시 ..

https://leetcode.com/problems/search-a-2d-matrix-ii/description Q. 주어진 행렬 m x n 이 아래와 같은 조건과 함께 주어질 때, target 값이 행렬내에 있는지 조회하라. 각 열과 행은 각각 오름차순으로 정렬되어 있다. Solution. 정렬되어 있으므로 binary tree를 쓰는 방법으로 가야 최적해가 나올 것 같다. 해당 열이나 행의 첫 값이 target보다 더 큰 값이면 해당 열이나 행은 조회에서 제외할 수 있다. 위 그림에서 x 축은 index 1(4)까지만, y 축은 index 2(3)까지만 target을 조회하면 되는 원리다. 더보기 C# bool searchValueBST(int[][] matrix, int y, int left, i..

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/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의 핵심은 이전 누적값에 영향을 받지 않게, 특정 위치에서 독립적으로 끝까지 계산한 결과를 갖도록 로직을 만들어야 하..