잊기싫어 메모장 잊기싫어 메모장

https://leetcode.com/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked 문제접근1. DFS를 사용하여 matrix 탐색2. Flag를 사용하여 matrix 탐색위 두 방법을 썼을 때에, 최소 O(mn) ( 어찌 되었든 모든 cell을 방문해야 함 ) 줄단위 처리를 고민하며 아래 코드를 작성특정 경우에 줄단위 처리를 하여 조금 더 빠를 수도 있음! spiral을 제어하는 move같은경우 enum으로 작성하면 더 좋을 수 있지만,귀찮았기 때문에,,,,정답코드0msBeats100.00%19.73MBBeats41.55% -> 0.6MB 차이더보기class Solution { func spiralOrde..

https://leetcode.com/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked 문제접근아이디어1주어진 매트릭스는 x,y가 증가하는 방향으로 이동하면 해당 index의 value가 증가한다.다만, (3,1)의 값이 (2,3) 보다 항상 크지 않다. 대소 비교는 각 행, 열 마다 개별적이다.bfs를 이용하여 조건에 맞는 index가 존재하는지 찾는다.아이디어2행 렬을 꼭 이동하지 않고, 그리디에 가깝게  풀어보기? 정답코드아이디어 1을 사용하여 정답을 맞춘 코드그런데, 129msBeats5.56% 로 성능이 좋지는 않다.더보기class Solution { struct Point: Hashab..

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked 문제접근DFS를 사용하여 p, q를 탐색탐색하며 지나온 TreeNode를 배열로 기록p,q를 찾았다면, 각자 지나온 기록 Treenode 배열에서 겹치는 마지막 element탐색탐색 결과 반환정답코드성능이 처참하다..831msBeats5.74%더보기/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * pu..

https://leetcode.com/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-100-liked 문제접근각 depth의 가장 우측의 Treenode.val을 상위depth부터 하위depth로 array로 반환해야 함.각 depth별 Treenode를 전부 알아야하기에, 전체 순환을 돌아야 한다고 생각약간의 꼼수?로 TreeNode의 갯수가 최대 100개이므로, 전체 순환을 돌아도 된다고 생각함.brutalForce에 가깝지만, queue를 사용하여 BFS한다. 이 때, 좌측 Treenode를 먼저 탐색한다좌측 먼저 탐색하여 가장 마지막에 해당 Depth에 탐색된 값을 사용한다정답코드map을 [Int: [Int]]구조로 사..

https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/ 문제접근반환해야할 정답 array인 sol의 정의는 다음과 같다.sol[i]는 아래의 조건을 만족해야한다.sol[i]는 nums 부분집합의 크기이다. 이 때, 부분집합의 크기가 최대여야 한다.nums의 부분집합은 합이 queries[i]보다 작거나 같아야 한다.정답코드해당 코드는 13ms Beats5.56%로 성능이 매우 좋지 않다.예상컨데, lastIndex를 찾는 반복문이 O(n^2)이기 때문이라 추측 시간 성능이 좋은 코드들을 찾아보니, lastIndex 구문을 binarySearch로 대체한 경우들이었다.더보기더보기class Solution { fun..

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked 문제접근아이디어 1 - root를 pre-order순서로 순회한다. array같은곳에 append해서 순서대로 저장. array를 순회하며 flatten형태로 변환아이디어 2 - root를 pre-order순서로 순회한다. left, right의 참조값을 지역 변수에 할당. left를 즉시 right에 할당. right는 후위를 방문 할 때 마지막으로 방문했던 node에 붙여준다. 아이디어 1은 구현하고, 읽기는 편하지만 여러모로 성능상 좋지 않아보인다.그래서 아이디어2로 구현하였다.그런데 문..

https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/description/ 문제 접근아이디어는 두 가지가 생각났다.node.val은 유니크하다. 그러므로 다익스트라 알고리즘으로 풀기최하단 노드로부터 depth를 계산하기 (dfs)정답 코드양방향 노드, 우선순위 Queue로 인해서 O(nlogn)처참한 성적642msBeats5.55% -> 95/100 ;;; 95등이라니!54.86MBBeats27.78%더보기더보기/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: Tre..

https://leetcode.com/problems/letter-combinations-of-a-phone-number/submissions/1585290142/?envType=study-plan-v2&envId=top-100-liked 문제접근1. digits을 적절한 알파벳들로 변형2. 기존 결과값에 해당 알파벳을 추가하여 대체정답코드더보기class Solution { func letterCombinations(_ digits: String) -> [String] { var sol = [String]() for digit in digits { var subset = [String]() let converted = transform..