Apes Together Strong.

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

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

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을 통째로 다시 할당 할 수 있다면 간단하다. 하..

https://leetcode.com/problems/spiral-matrix/description Q. m x n matrix가 주어질 때, 모든 matrix의 값을 나선 형태로 반환하라. Solution. 나선으로 하나씩 돌게 로직을 만들다 보니, 예외 상황이 많이 생긴다. 따라서 메모리를 조금 더 쓰고, 간결한 접근법을 찾는다. 외피부터 시계방향으로 데이터를 얻는다. map, dictionary를 사용해, 중복을 방지 한다. 다음 한단계 내피(x+1, y+1)로 들어온다. 이 과정을 Width/2 까지 진행한다. 많은 중복이 생기겠지만, 로직을 단순화 하고, set 자료구조를 써서 중복데이터를 억제한다. 더보기 int CellToIndex(int iX, int iY, int W) { return W..

https://leetcode.com/problems/reverse-linked-list Q. 주어진 리스트를 뒤집어라. Solution. 현재 노드의 '다음' 포인터를 '이전' 노드로 설정한다. 이것의 반복이 다 이다. public ListNode ReverseList(ListNode head) { ListNode node = head; ListNode prev = null; while(node != null) { ListNode next = node.next; node.next = prev; prev = node; node = next; } return prev; } 적절한 결과. 이 문제와, 리스트를 반으로 자르는 문제는 linked list의 기본이 되는 문제다. 완전히 숙지하는 것이 좋을 것이다.

https://leetcode.com/problems/intersection-of-two-linked-lists/description Q. 두개의 노드가 도중에 교차할 때 해당 교차지점을 찾아서 반환하라. Solution 방법을 알면 간단한 문제다. 시작 지점을 align 시키는 것이 키인데, 보통의 풀이법은 두 리스트를 하나씩 전진시켜, 끝에 도달하면 반대 쪽 head에서 다시 출발한다. 이때 재출발 후, 두 노드가 만나는 지점이 교차점이 된다. 두 노드의 오프셋이 다르므로 이를 다른 노드의 시작점으로 재출발 시키면서 오프셋을 동기화 시킨 것이다. 더보기 public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode node..

Q. 주어진 리스트를 오름차순 정렬하라. 이때 정렬시간을 O(nxlogn) 으로 하여라. Solution. 분할 정렬 하라는 것이다. 분할 병합 정렬을 하기 위한 방법을 정리 해 본다. 우선 list를 2개로 계속 나눈다. 리스트가 하나의 노드만 가질때까지 계속 쪼갠다. 이후로 작은 것 먼저 이어서 위로 반환한다. 분할 조립이 분할/순차적으로 되어야 하므로, 재귀함수가 필요하다. 로직대로 코드를 만든다. 더보기 public ListNode SortList(ListNode node) { // 1개의 노드(이하)가 되면, 그냥 반환한다. if(node == null) return null; if(node.next == null) return node; // break list. ListNode fast = ..