silvergoni.builder()

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

문제 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

문제 https://leetcode.com/problems/unique-paths/ 문제 풀기 전 기존에 풀었던 최단거리구하는 64. Minimum Path Sum 을 풀었던 터라 dp로 접근하면 되겠다 싶었다. 직접 푼 풀이 소요시간: 6분(08:37 ~ 08:43) class Solution { public int uniquePaths(int m, int n) { int[][] board = new int[m][n]; for(int i=m-1; i>=0; i--) { for(int j=n-1; j>=0; j--) { if (i == m-1 || j == n-1) { board[i][j] = 1; } else { board[i][j] = board[i+1][j] + board[i][j+1]; } } }..