silvergoni.builder()

문제 https://leetcode.com/problems/path-sum-iii/ 문제 풀기 전 배열이 앞,뒤 접근을 고민했다면 트리는 위아래 출발을 고민한다. 위에서 출발하면 넘겨주는 파라미터를 배열로 해서 합한값, 본인을 내려주면 될거같다. 위에서 접근하는 방식을 취해보자 직접 푼 풀이 소요시간: 14분(09:31 ~ 09:45) class Solution { private int count=0; public int pathSum(TreeNode root, int sum) { pathSum(root, sum, new ArrayList()); return count; } private void pathSum(TreeNode root, int sum, List list) { if (root == nul..

문제 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 문제 풀기 전 recursion으로 비교를 수행한다. recursion식은 리턴: profit 비교: profit으로 한다. 직접 푼 풀이 소요시간: 50분(08:00 ~ 08:50) 못풀었다. 재도전하기! 느낀점 위의 recursion으로는 풀지 못했다. 정확히는 풀었는데 속도 제한에 걸렸다. 실제로 모든 테스트에 통과하였으나 시간초과로 안된다고 결과가 나왔다. 이 문제를 접근할때 이렇게 했으면 더 좋았을거 같다. 일단 자료형을 파악하는 것이다. 다행히 문제에 배열로 잘나와서 이 단계는 쉽다. 그 다음 배열이라면 앞에서부터 접근할지, 뒤에서 부터 접근할지를 고민..

문제 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/letter-combinations-of-a-phone-number/ 문제 풀기 전 이렇게 출력하는 문제를 보면 재귀로 다 돌려야한다. 보통이런걸 조건에 따라 돌리기때문에 backtracking이라고 한다. 직접 푼 풀이 소요시간: 22분(13:12 ~ 13:34) class Solution { private String[][] phoneText = new String [][]{{" "}, {}, {"a","b","c"}, {"d","e","f"}, {"g","h","i"}, {"j","k","l"}, {"m","n","o"}, {"p","q","r","s"}, {"t","u","v"}, {"w","x","y","z"} }; private Lis..

문제 https://leetcode.com/problems/sort-colors/ 문제 풀기 전 quick sort로 풀라는 걸로 들렸다. Lumoto방법만 알고 있었는데 hoare방법으론 안풀었는데 중복이기에 hoare방법으로 풀어야햇다. 직접 푼 풀이 재도전하기 느낀점 결론적으로 못 풀었다. hoare's방법을 봤을때 이해했다고 생각했는데 직접 짜보지 않아서인지 이해한게 아니었다. 근본적으로 lumoto와 접근방법이 다르다. lumoto는 요소하나를 중심으로 낮은거 높은거를 나누고 hoare는 그 중간요소를 찾는것부터 시작한다. 그 중간요소를 왼쪽 오른쪽으로부터 접근을 시작해서 찾고 그 다음에 그걸 중심으로 subarray를 재귀적으로 계산한다. "347. Top K Frequent Eleme..

문제 https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 문제 풀기 전 preorder를 기준으로 inorder를 쪼개면 되겠다. 이런문제 나오면 배열을 복제하고 싶지만 결코 그건 답이 될 수 없다. 직접 푼 풀이 소요시간: 74분(19:55 ~ 21:09) class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return makeTree(preorder, 0, inorder, 0, inorder.length); } public TreeNode makeTree(int[] preorder, int index, int[]..

문제 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/house-robber-iii/ 문제 해설 이 문제는 부모자식 트리로 직접 연결된 경우는 안되고 한칸 뛰어서는 도둑질이 가능한 문제이다. 문제 풀기 전 dp문제인걸 알았다. 이전결과가 현재결과를 얻는데 필요하니 말이다. 하지만 문제를 풀지는 못했다. 자바에서는 리턴을 하나라는 고정관념에 잡혀서 였다. 직접 푼 풀이 재도전하기 느낀점 리턴을 여러개 하고 싶으면 배열을 만들어서 쓰면 되었다. 사실 간단한 방법인데 자바에서는 잘 안쓰는 형식이기에 다른 방법이 있겠지하다가 결국 못 풀었다. 리턴에서 2개를 갖고 있어야하는데 바로 전단계와 , 전전단계의 데이터가 있어야 지금의 단계와 합할지 말지를 결정할 수 있기 때문이다. 아래는 솔루션에서 영감을 얻어 ..