Apes Together Strong.

https://leetcode.com/problems/partition-list/description  Q. 리스트가 주어질 때, x 보다 작은 값, 큰 값으로 노드를 구분하고 연결하라.  Solution.  해당 값을 기준으로 node를 재연결 하고,  해당 두 connection head를 연결해 준다.   코드. 더보기public ListNode Partition(ListNode head, int x) { ListNode node = head; ListNode part1 = null, part2 = null; ListNode n1 = null, n2 = null; while(node != null) { if(node.val   결과.

https://leetcode.com/problems/rotate-array/description Q. 정수배열 nums가 주어질 때, k 만큼 배열을 rotate하여라. 추가 메모리를 사용하지 말아라.   Solution.  고전과도 같은 문제이다.   추가 메모리를 사용할 수 있다면, 간단하다.  오프셋 k 만큼 이동시켜 새 버퍼에 쓰면 된다.   추가 메모리를 쓰지 않으므로, 다른 접근이 필요하고, 이에 대해 알려진 알고리즘을 쓴다.   배열 전체를 reverse한다.  앞에서 k 개 만큼 reverse한다.  이후 위치에서 array.Length - k 만큼 reverse한다.   이것이 결과가 된다.   만약 문제 질의가 left로 회전하지 않고 right로 회전한다면 어떨까? 그 경우도 약간의..

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

https://leetcode.com/problems/find-all-anagrams-in-a-string/description Q. 두개의 string s와 p가 주어질 때, p의 anagram이 되는 s의 substring을 찾고, 그 시작 index 목록을 반환하라. Solution p에 대해 frequency buffer를 만들고 해당 버퍼를 모두 가진 구간이 있는지 확인한다. 비교적 간단한 문제. 코드. 더보기 public IList FindAnagrams(string s, string p) { IList ret = new List(); Dictionary dictFreq = new Dictionary(); for(int q = 0; q < p.Length; ++q) { if(dictFreq.C..

https://leetcode.com/problems/minimum-window-substring/description Q. s와 t 두개의 문자열이 주어질 때, t의 모든 문자가 나타나는 s 의 sub string 중 최소 길이를 갖는 sub string을 찾아라. Solution. 모든 t가 s에 출현해야 하고, t에 중복된 문자가 존재 할 수 있으므로, hash를 써서 문자 freq buffer를 사용해야 할 듯 하다. 슬라이딩 윈도우 기본 로직에 맞게 모든 문자열을 찾으면 해당 sub string을 찾고 최소 길이인지 확인한다. 이후 left에 대해 다음 t에 나오는 char가 나오는 시점까지 left를 당긴다. 그대로 위 로직을 반복한다. 로직대로 코드를 써 본다. 더보기 public strin..

https://leetcode.com/problems/longest-substring-without-repeating-characters/description Q. 주어진 문자열 s 에서 문자가 중복되지 않는 최대 sub string의 길이를 찾아라. Solution. Sliding window + hash 문제. 중복이 생기면, left를 중복이 생기지 않을 때 까지 당긴다. 더보기 public int LengthOfLongestSubstring(string s) { Dictionary dictBuff = new Dictionary(); int left = 0, right = 0; int maxLen = 0; for(; right < s.Length; ++right) { char cur = s[righ..

https://leetcode.com/problems/set-matrix-zeroes/description Q. 주어진 m x n 행렬에서 0 인 원소가 있다면, 그 열과 행을 모두 0으로 치환하라. 추가 메모리를 사용하지 말아라. Solution. 위 그림처럼 도중에 0이 생기면 해당 열과 행이 0으로 overwrite 된다. 추가 메모리를 사용하면, 간단하다. 하지만, 문제에서 사용할 수 없다. 0을 만날 때 해당 행과 열을 0으로 만들면, 기존 data가 overwrite되므로, 올바를 결과를 만들 수 없다. 따라서 적절한 위치에 loop up table data를 써야 한다. 우선 추가 메모리를 쓸 수 있다면 얼마면 되겠는가 생각해 본다. m x n을 통째로 다시 할당 할 수 있다면 간단하다. 하..