silvergoni.builder()

문제 https://leetcode.com/problems/longest-increasing-subsequence/ 문제 풀기 전 rescursion으로 풀 수 있을거라 생각했다. 대신 영향받는것과 가져와야될 것을 먼저 정의 해봤다. (index, number) -> count index는 이전까지 진행했던 index 이전 Index중에서 number는 가장 큰 값 직접 푼 풀이 소요시간: 30분(08:50 ~ 09:20) class Solution { private int[] cache; public int lengthOfLIS(int[] nums) { cache = new int[nums.length]; Arrays.fill(cache, -1); int ret = 0; for (int i=0; i

문제 https://leetcode.com/problems/palindromic-substrings/ 문제 풀기 전 brute force로 풀었다. 직접 푼 풀이 소요시간: 10분(19:54 ~ 20:04) //visted를 이용해 recursion class Solution { private int[][] visited; public boolean searchMatrix(int[][] matrix, int target) { visited = new int[matrix.length][matrix[0].length]; for (int i=0; i

문제 https://leetcode.com/problems/partition-equal-subset-sum/ 문제 풀기 전 (잘못된 생각) 정렬한다음에 앞에서 출발해서 더하고, 뒤에서 부터 출발해서 더하면 되지 않을가. (잘못된 생각) 역시 합문제는 더하고 봐야된다. [1,1,2,2]는 안되는구나 (잘못된 생각) 같은 숫자 쌍은 없애자. [1,5,5,11] 39. Combination Sum 하고 비슷한 느낌을 받았다. 직접 푼 풀이 소요시간: 41분(17:17 ~ 17:58) class Solution { private int[][] cache; public boolean canPartition(int[] nums) { int sum = 0; for (int num: nums) { sum += num;..

문제 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 문제 풀기 전 일단 두 노드를 찾는다. 두 노드의 부모를 비교하면서 제일 가까운 부모를 찾는다. 이렇게 해도 logN 으로 걸릴것이다. 직접 푼 풀이 소요시간: 41분(22:36 ~ 11:17) class Solution { private boolean found = false; private LinkedList gstack; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { find(root, p, new LinkedList()); LinkedList pQueue = gstack; p..

문제 https://leetcode.com/problems/perfect-squares/ 문제 풀기 전 이런 문제는 앞에서 접근할지, 뒤에서 접근할지 결정해야하는데 숫자가 커짐에 따라 앞에 숫자를 알고 있으면 계산이 빨라질 수 있으니 이건 앞에서부터 세야한다. 이렇게 앞에것이 뒤에 결과에 도움을 주면 보통 dp로 풀리니 그 점도 염두하면 좋다. 직접 푼 풀이 소요시간: 42분(07:07 ~ 07:49) class Solution { public int numSquares(int n) { int[] box = new int[n+1]; int index = 1; for(int i=1; i= Math.pow(index, 2)) { index++; } int min = Integer.MAX_VALUE; for(..

문제 https://leetcode.com/problems/task-scheduler/ 문제 풀기 전 영어 알파벳 대문자로 제한되므로 배열을 쓸 수 있겠다. 제일 많은걸 찾아서 기준을 잡아야겠다. 제일 많은것들이 여러개일때를 고려해야겠다. 제일 많은 것을 기준으로 세웠을때 나오는 빈공간의 수와 남아있는 수를 비교해야겠다. 직접 푼 풀이 소요시간: 37분(22:00 ~ 22:37) class Solution { public int leastInterval(char[] tasks, int n) { int[] alphabets = new int[26]; for (int i=0; i

문제 https://leetcode.com/problems/implement-trie-prefix-tree/ 문제 풀기 전 Trie를 어렴풋하게 기억하기로는 단어별로 쪽개서 포도송이처럼 만드는 자료형이었다. 이번에 제대로 구현해볼 기회가 생겼다고 생각했다. 직접 푼 풀이 소요시간: 24분(20:46 ~ 21:10) class Trie { List tries; char sub; boolean hasWord; /** Initialize your data structure here. */ public Trie() { hasWord =false; tries = new ArrayList(); } /** Inserts a word into the trie. */ public void insert(String wor..

문제 https://leetcode.com/problems/palindromic-substrings/ 문제 풀기 전 subset 어떻게 풀었더라 checkPalindromic 시작점, 끝점 메소드를 이용하면 좀 더 빨라지겠다. 직접 푼 풀이 소요시간: 15분(18:19 ~ 18;34) #Brute force class Solution { public int countSubstrings(String s) { int n = s.length(); int count = 0; for (int k=1; k

문제 https://leetcode.com/problems/daily-temperatures/ 문제 풀기 전 현재 시점에 영향주는 데이터는 지금의 데이터와 비교해서 높은 숫자가 나올때만 한번에 여러개에 영향을 주는걸 어떻게 풀것인가. 직접 푼 풀이 소요시간: 6분(18:07 ~ 18:13) class Solution { public int[] dailyTemperatures(int[] T) { int[] result = new int[T.length]; for(int i=0; i= T[stack.peek()]) stack.pop(); result[i]=stack.isEmpty() ? 0 : stack.peek()-i; stack.push(i); } return result; } }누적되는 알고리즘 접근 ..

문제 https://leetcode.com/problems/subsets/ 문제 풀기 전 rescursive하게 풀되 중간중간에 저장하면 되겠다. 예전에 Permutations처럼 구하되, 중간중간에 저장만 잘하면 되겠는걸. 직접 푼 풀이 소요시간: 15분(10:46 ~ 11:01) class Solution { private Set result = new HashSet(); public List subsets(int[] nums) { result.add(new ArrayList()); doSubSets(nums, 0, new int[nums.length]); return result.stream().collect(Collectors.toList()); } private void doSubSets(int..