Apes Together Strong.

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/ 문자열이 주어질 때, char의 중복이 없는 가장 긴 sub string의 길이를 구하라.  전형적인 sliding window 문제. 중복이 생기면 중복이 제거될 때까지 right를 당긴다.  코드 더보기int lengthOfLongestSubstring(string s) { int left = 0, right = 0; set setBuff; int maxLen = 0; for (; right   결과

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ 주식 가격이 주어진다. 이때 어느 하루에 사고, 어느 다른 하루에 판다면, 이 수익의 최대값을 구하라. 파는 날은 반드시 사는 날과 다른 이후의 날이어야 한다. 사는 날은 최대한 싸면 큰 차익의 결과가 기대될 것이다. 따라서 최소값에서 사고, 알수 없는 모든 값들에 대해 차(수익)의 최대값을 구한다. 코드 더보기int maxProfit(vector& prices) { if (prices.size()   결과

https://leetcode.com/problems/container-with-most-water/description/ 아래와 같이 수조가 있으며, 이때 높이의 배열이 주어진다. 물을 가장 많이 담은 때의 물의 면적을 구하라.  양 수조의 기둥을 좁히며 면적을 구한다. 면적은 간단히 구할 수 있다. 문제는 좁히는 방법이다. 양옆 기둥의 높이 중, 작은 쪽을 변경시켜 더 큰 결과를 얻는 것을 유도한다.  코드. 더보기int maxArea(vector& height) { int left = 0; int right = height.size() - 1; int maxArea = 0; while (left height[right]) --right; ..

https://leetcode.com/problems/3sum/description/  정수 배열이 주어질 때, 세 수의 합이 0 이 되는 수를 찾아라. 우선 정렬이 필요하다. 다음으로 첫수를 정하고, 그 뒤로는 두 수의 합을 구하는 로직과 같다.  다만, 중복이 없어야 하므로, 이는 여러 방법을 사용할 수 있겠다.  코드  더보기vector> threeSum(vector& nums) { sort(nums.begin(), nums.end()); vector> vRet; set vBuff; for (int q = 0; q { num0, nums[left], nums[right] }); vBuff.insert(temp); } ..

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ 주어진 정수 배열이 정렬되어 있을 때, 두 수의 합이 target이 되는 1based index를 출력하라. 정렬되어 있으므로, left, right를 이용하여 수의 범위를 좁힌다. target보다 sum이 크면 작아져야 하므로, right를 낮춘다. target보다 sum이 작으면 커져야 하므로, left를 높힌다.  코드 더보기vector twoSum(vector& numbers, int target) { int left = 0; int right = numbers.size() - 1; vector vRet; while (left { left+1..

https://leetcode.com/problems/valid-palindrome/description/  주어진 string에서 알파벳이 아닌 문자를 제외하고 palindrome인지 확인하라.   다양한 방법으로 풀수 있겠다.  문제 제시대로 직관적으로 풀어본다.  코드 더보기bool IsAlphabet(char a){ if (a >= 'a' && a = 'A' && a = '0' && a = 0 && !IsAlphabet(s[right])) --right; if (left >= s.size() || right   결과.

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; ..