Apes Together Strong.

https://leetcode.com/problems/single-number Q. 주어진 배열에 정수값이 하나만 제외하고 모두 두개씩 들어있다. 이 하나의 값을 찾아라. 이때 O(N) TC에 추가 메모리를 사용하지 말아라.  Solution.  map같은 것을 쓰면 금방 찾을 수 있지만, 문제에서는 leaner TC에 추가 메모리를 사용하지 말라고 했다.  따라서 다른 접근이 필요하다.  여기에서 XOR 개념이 필요하다. 아래에서 보는 바와 같이 XOR 연산은 두 값이 다른 경우 1을 돌려준다.  이 성질을 이용한다.   public int SingleNumber(int[] nums) { int ret = nums[0]; for(int q = 1; q    적절한 결과.

https://leetcode.com/problems/sort-colors/description Q. 주어진 배열을 각각 R, G, B color값을 의미한다.  이 배열을 정렬하라.   Solution.  count sort의 좋은 예시.   각 값을 카운팅 하고 그 숫자대로 배열을 다시 채운다.  public void SortColors(int[] nums) { int t0 = 0, t1 = 0, t2 = 0; for(int q = 0; q   적절한 결과.

https://leetcode.com/problems/merge-intervals/description Q. 구간의 배열이 주어질 때, 겹치는 구간에 작은 구간을 포함 할 수 있다.  이렇게 Merge를 하라.  Solution.  두 구간 값을 cX, cY 라고 해 본다. 예제를 보면 알 수 있지만, 핵심은 cY와 다음의 cX 가 겹치는가가 중요하게 작용을 한다.  즉, 현재의 cY가 다음의 cX 보다 크거나 같으면, 현재 구간을 다음 구간과 병합하면 되는 것이다.  다만, 이 전에 cX에 대해 모든 두간 배열이 정렬되어 있어야 하겠다.   로직대로 코드를 만들어 본다.  더보기 public int[][] Merge(int[][] intervals) { Array.Sort(intervals, (a..

https://leetcode.com/problems/maximum-subarray/description Q. 주어진 숫자배열의 최대 부분합을 구하라.   Solution.  2 중 loop를 돌면 풀이는 간단해 진다.  하지만, O(N)에 구할 방법을 고민해 보자.   여기서 잘 알려진 알고리즘이 dynamic programming을 활용한, 방법이다.  즉, 이전까지의 부분합의 최대값에 현재위치값을 더한 최대값이 현재의 최대 부분합이 된다는 것이다.   이것을 Kadane's Algorithm이라 하며, 이 알고리즘은 꽤 유명하다.   이것을 토대로 코드를 만들어 본다.  더보기 public int MaxSubArray(int[] nums) { // 주어진 배열에서 최대의 합을 가진 subArr..

https://leetcode.com/problems/first-missing-positive/description  Q. 정렬되지 않은 정수 배열 nums가 주어질 때, 배열안에 없는 가장 작은 양수를 찾아라.  O(N)의 TC에 O(1)의 space를 사용하라.  Solution 추가 메모리를 쓰면 간단하다.  하지만, 여기서는 그렇게 하면 안되므로, 다른 방법을 고려한다.   존재하는 수를 특정 방식으로 걸러내에 존재하지 않는 수를 찾아낸다.  여기서는 음수화를 취한다.   우선 루프를 돌며, 해당 값을 nums 배열과 매칭 시킨다면, 범위 바깥이 될 수를 골라내 범위 안 최소 값으로 초기화 한다. 모든 수가 존재한다면, 범위 밖 수는 없게 된다.   이 값을 index로 변환하고, 이 index위..

https://leetcode.com/problems/next-permutation/description Q. 주어진 정수 배열 nums에서 다음 permutation 값을 찾아라.  Solution 이런 문제를 보면 아직도 정말 배워야 할 것이 넘침을 느낀다.  직관으로 풀기는 힘든 문제.   관련 알고리즘을 찾아본다.   우선 nums[i]  이 피봇 포인트를 기준으로 뒤편의  값 중 피봇 포인트보다 큰 수장 가장 작은 값을 찾는다.  이 값과 피봇 포인트 값을 교체한다.  그리고 피봇 포인트 우측편 값들을 오름차순 정렬한다.  ( Reference : https://yoongrammer.tistory.com/109 )  이것이 원하는 답이 된다.   로직대로 코드를 만들어 본다.  더보기public..

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/valid-parentheses/description Q. 주어진 문장 s 에 (, {, [, ], }, ) 가 있다. 이 문장이 유효한지 판단하라. Solution. Parentheses 문제가 나오면 대부분 stack을 쓴다. 그 중에 쉬운축에 속하는 문제. 닫히는 기호가 나올 때 stack안의 top이 그에 상응하는 기호를 가지고 있는 지 판단한다. 더보기 public bool IsValid(string s) { Stack sBuff = new Stack(); for(int k = 0; k < s.Length; ++k) { if(s[k]==')' || s[k]=='}' || s[k]==']') { if(sBuff.Count == 0) return..