silvergoni.builder()

문제 https://leetcode.com/problems/minimum-path-sum/ 문제 풀기 전 이건 왠지 dp로 풀 수 있을거같다는 감은 왔다. 직접 푼 풀이 소요시간: 40분 재도전하기 느낀점 결국 brute force로도 못 풀었다. dp로 푸는방식이 있다. 아래와 같다. 결국 dp로 푸는것은 지금의 값을 결정하는 요소들의 비교가 아닐까 하다. 아래 푸는 방식을 보면 합해진 값의 오른쪽과 합해진 값의 아래쪽 중에 작은걸 선택해서 0,0까지 더하는 방식인데 이걸 잘 기억해두면 다음법 dp스러운 문제를 봐도 힌트가 될 것이다. 솔루션 공부 후 추가로 푼 풀이 class Solution { public int minPathSum(int[][] grid) { for (int i=grid.lengt..

문제 https://leetcode.com/problems/find-the-duplicate-number/ 문제 풀기 전 제한조건을 부분적으로 만족한다면 HashSet으로 풀어 볼 수 있다. 제한조건을 부분적으로 만족한다면 Arrays.sort으로도 풀어 볼 수 있다. 직접 푼 풀이 소요시간: #HashSet 풀이 class Solution { public int findDuplicate(int[] nums) { Set set = new HashSet(); for(int i=0; i

문제 https://leetcode.com/problems/combination-sum/ 문제 풀기 전 recursion으로 풀면되겠다. Group Anagrams 풀었던 걸 이용했다. 여기도 역시 중복을 하나로 체크해야하는데 그때 알파벳키를 만들었던것처럼 키를 만들어 유일값을 체크하면 되겠다 싶었다. 직접 푼 풀이 소요시간: 24분(20:12 ~ 20:36) class Solution { List result = new ArrayList(); Set checkBox = new HashSet(); public List combinationSum(int[] candidates, int target) { doCombinationSum(candidates, target, new ArrayList()); ret..

문제 https://leetcode.com/problems/rotate-image/ 문제 풀기 전 반시계로 돌릴 수 있을가 했는데 왠지 복잡할거 같다. swap을 하면되겠다. 내려가는 대각선으로 한번, 좌우로 한번 직접 푼 풀이 소요시간: 8분(21:17 ~ 21:25) 30분(21:27 ~ 21:57) #대각선 한번 + 좌우로 한번 회전 class Solution { public void rotate(int[][] matrix) { for (int i=0; i

문제 https://leetcode.com/problems/product-of-array-except-self/ 문제 풀기 전 다 곱해서 하나씩 나누면 O(n)이나 나누기를 쓰지말라는 조건에 걸린다. 하나빼고 다 곱하면 O(n^2)으로도 풀 수는 있다. 그전까지의 곱을 모두 저장하고 있다면 계산이 좀 빠르지 않을까. 직접 푼 풀이 소요시간: 47분(21:08 ~ 21:55) 재도전하기 끝내 풀지 못했다. 느낀점 지금까지 문제를 30개정도 풀었는데 이건 진짜 멋진 문제다. 풀이에 대한 고정관념(다 곱한것에서 하나만 나눈다)를 막으니 분명 쉬운 문제같은데 풀리지가 않았다. 아직 멀었다. 그리고 솔루션을 확인하고 나서는 진짜 멋있는 문제라고 생각했다. 개념은 사실 left, right에 있었다. 꼭 다시 풀어..

문제 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/kth-smallest-element-in-a-bst/ 문제 풀기 전 kth 나오자 마자 bst는 보지못하고 priorityQueue라고 생각하였다. 순회해서 다 저장하고 priorityQueue로 해결할 수 있겠다. 다 오른쪽으로 줄세워서 priorityQueue로도 풀 수 있겠다. 94번 문제 풀이에서 사용했던 Morris Traversal를 이용해서이다. 직접 푼 풀이 소요시간: 7분(09:40 ~ 09:47) #1. 순회해서 다 저장하고 priorityQueue로 해결 class Solution { public int kthSmallest(TreeNode root, int k) { PriorityQueue pq = new PriorityQ..

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

문제 https://leetcode.com/problems/permutations/ 문제 풀기 전 딱보니 result는 전역변수로 해서 recursion이 끝날때마다 add하는 형식으로 해야겠다. 메소드를 하나 더 두고 index를 하나씩 추가해서 끝을 파악핟록 짜야겠다. 채워져가는 배열이 하나 더 있어야겠다. 직접 푼 풀이 소요시간: 14분 (11:56 ~ 12:10) class Solution { private List result; public List permute(int[] nums) { result = new ArrayList(); doPermute(nums, 0, new int[nums.length]); return result; } private void doPermute(int[] num..