Apes Together Strong.

https://leetcode.com/problems/group-anagrams/description Q. 주어진 문자열 목록 strs 에 대해 서로 anagrams 인 것들에 대해 묶어서 출력하라.   Solution 여러 풀이가 있을 수 있다.   Frequency buffer를 사용하면, 각 문자당 freq buffer를 만들고,  해당 버퍼가 같다면, anagram 하다고 판단할 수 있다.  하지만 O(NxN)의 TC가 소요되고, 역시나 Time limitation 오류가 생긴다.   다른 접근을 해 본다.  문자를 같은 원리에 의해 재 조립하면, 같은 문자를 가진 단어는 같은 문자 순서를 가질 것이다. 즉, string을 정렬해 본다.   정렬에 O(N x logN), map 비교에 N 즉, 최..

https://leetcode.com/problems/valid-anagram/description Q. 주어진 문자열 t와 s가 anagram 한지 판단하라.   Solution.  Anagram의 특성을 이용하여 한 string에 frequency buffer를 만들고 다른 문장에서 이것과 비교한다.  public bool IsAnagram(string s, string t) { Dictionary dictFreq = new Dictionary(); for(int q = 0; q   결과.

https://leetcode.com/problems/word-pattern/description Q. pattern과 단어 문자열 s 가 주어질때, 패턴과 문자열이 일치하는지 판단하라.   Solution.  최대한 단순하게 접근하고 TC는 O(N)으로 제한한다.   우선 s의 단어셋과 pattern의 길이가 다르면 무조건 일치하지 않게 된다.   다음으로 s의 단어셋을 풀어 hashset을 만들어 놓는다. 이 수대로 다른 단어가 존재 한다는 것이다.   마지막으로 pattern을 순회하며, 각 패턴의 캐릭터 별로 단어가 일치하는지 확인한다.   모두 통과하고 hashset의 수가 패턴의 단어수와 같다면, 일치하는 것으로 판단할 수 있다. 더보기 public bool WordPattern(string ..

https://leetcode.com/problems/isomorphic-strings/description Q. 두개의 문자열 s 와 t 가 주어 질때, isomorphic 한지 판단하라.  Solution.  즉, 캐릭터의 출현 빈도, 변환된 위치 등이 같다면 isomorphic 하다고 할 수 있겠다.  여러가지 방법을 활용 할 수 있겠다. 최대한 간단하게 freq buffer와 위치 체크 등을 이용한다.  더보기public bool IsIsomorphic(string s, string t) { if(s.Length != t.Length) return false; Dictionary dictFreqS = new Dictionary(); for(int q = 0; q di..

https://leetcode.com/problems/ransom-note/description Q. 주어진 두개의 문자열 ransomNote와 magazine이 있다. magazine의 단어로 ransomNote의 문장을 구성할 수 있는지 여부를 반환하라.   Solution.  hash 류의 간단한 문제.  public bool CanConstruct(string ransomNote, string magazine) { Dictionary dictFreq = new Dictionary(); for(int q = 0; q    결과.

https://leetcode.com/problems/game-of-life/description Q. 2차 정수 행렬 board가 주어진다. 1이 live, 0이 dead를 의미할 때, 다음에 의해 다음 상태를 구하라.  - live cell일 시, 주변에 live cell이 2개보다 적다면 dead 된다.  - live cell일 시, 주변에 live cell이 2개 혹은 3개 라면 live cell이 된다.  - live cell일 시, 주변에 3개 이상의 live cell이 있다면 dead cell이 된다.  - dead cell일 시, 주변에 3개의 live cell이 있다면 live cell이 된다.  추가 메모리 할당을 하지 말아라.   Solution.  우선 문제 해석을 정확하게 하자. ..

https://leetcode.com/problems/valid-sudoku/description Q. 유효한 sudoku인지 판단하라.   Solution 위 3 조건을 체크하는 로직을 만든다.   다양한 방법이 있을 수 있다고 본다.   최대한 간단하게 만들어 본다.더보기 bool IsValid(char ch, HashSet cache){ if(ch'9') return false; if(cache.Contains(ch)) return false; return true;}public bool IsValidSudoku(char[][] board) { // Row check. for(int y = 0; y buff = new HashSet(); ..

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description Q. 문자열 s와 단어 배열 words가 주어질 때, words를 조합해서 구성할 수 있는 문자열이 s에 존재하면, 그 시작 위치 index를 반환하라.  Solution.  우선 문자열을 확인 할 frequency buffer가 hash type으로 필요하다.  그리고 sub string을 left to right 로 sliding 해 가면서 check 한다.   도중에 실패하면, 바로 다음 위치에서 시작한다.  성공한 문자를 찾아도 시작지점 바로 다음 위치에서 시작한다.   로직을 코드로 작성한다.더보기bool IsStartWith(string s, i..

https://leetcode.com/problems/minimum-size-subarray-sum/description  Q. 주어진 정수 배열 nums에 대해서 그 sub array 합이 target보다 크거나 같은, 최소 subarray 길이를 찾아라.    Solution 푸는 과정이 sliding window라는 것을 알면 쉬운 문제.   윈도우의 합이 target이상인 구간에서 길이를 최소 길이로 갱신하고,  left 를 당기며 구간 합에서 left를 제거한다.   위 로직의 연속. public int MinSubArrayLen(int target, int[] nums) { int left = 0; int right = 0; int sum = 0; int minLen = ..

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description  Q. 오름차순 정렬된 정수배열 numbers가 주어질 때, 두 수의 합이 target이 되는 두 index를 찾아라.   Solution.  정렬된 배열이 주어지면, 대다수 검색 방법이 정해져 있다.   Binary Search를 사용하도록 한다.   어떤 대상에 대해?  현재 값과 그 합이 target이 되는 수를 검색하면 된다.   코드를 작성해 본다. int findNum(int[] numbers, int target, int left, int right){ if(left > right) return -1; int mid = left + (right..