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/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개를 갖고 있어야하는데 바로 전단계와 , 전전단계의 데이터가 있어야 지금의 단계와 합할지 말지를 결정할 수 있기 때문이다. 아래는 솔루션에서 영감을 얻어 ..

문제 https://leetcode.com/problems/decode-string/ 문제 풀기 전 stack으로 풀 수 있겠다. ]문자가 나오기전까지 stack에 넣다가 나오면 pop한다. [문자가 나올대까지 하고 그다음 숫자를 나오게 해서 그려준다. 숫자는 한자리가 아니기때문에 숫자는 특별히 하나의 문자로 만들어서 stack에 넣어줬다. 직접 푼 풀이 소요시간: 36분(21:51 ~ 22:27) class Solution { public String decodeString(String s) { LinkedList stack = new LinkedList(); String sub = ""; for (int i=0; i

문제 https://leetcode.com/problems/unique-binary-search-trees/ 문제 풀기 전 처음에는 subarray로 푸르는데 recursive가 헷갈려서 중단 이게보니 정렬된 요소의 갯수에 따라 답이 정해져 있음 1->1 2->2 3->5 직접 푼 풀이 소요시간: 36분(08:48 ~ 09:24) class Solution { public int numTrees(int n) { int[] elements = new int[n]; int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int j=2; j