wanna be a software craftman step by step

난이도는  Easy 인데, Acceptance 는 32% 여서, 뭐지 하고 봤다. 처음엔 쉽게 봤는데, 결국 못풀었다. 26진수나 마찬가지라고 생각해서, % 와 / 연산을 사용했는데. 접근이 비슷하긴 했는데 아주 틀렸다. 문제에서 주어지기로는 A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 이런식으로 주어졌다.  문제는, 26진수라고 했을때, 1에서 26까지 가는걸 A 에서 Z 까지 간다고 생각할 수는 있는데,  0이 없다.  10진수의 경우, 0부터 시작해서 9까지 간 다음, 10 으로 가는데. 이건 시작이 1이다. 일반적인 26진수라면  0 -> A 1 -> B 25 -> Z 26 -> BA (= B*26+A*1) 27 -> BB (= B*26+B*1) 이런식으로 간다. 그런데 위의 경우에는 1 -> A 2 -> B 26 -> Z 27 -> AA (= A*26+A*1) 28 -> AB (= A*26+B*1) 이와같이 움직였다. 1,2,3,... 9 다음에 10이 아닌 11이 오는거나 마찬가지인 셈이다....? 음.. 모르겠다. 설명을 봐도. 이해를 못하겠다. 일단 패스.  https://leetcode.com/problems/excel-sheet-column-title/discuss/441430/Detailed-Explanation-Here's-why-we-need-n-at-first-of-every-loop-(JavaPythonC%2B%2B)

이전에 비슷한 접근법을 요구하는 문제가 있었는데, 그 기억대로 접근해서 한번에 해결. 무식하게 매번 전체 array 를 search 할수도 있는데 그러면 Time limt exception 이 뜰거라고 생각했다. 그런데 그렇게 해서도 accept  가 된 솔루션이 있어보이긴 했지만 아무튼. 요지는 두  array 를 관리 하면서, 현재  price 와 span 을 기록하는데, 현재를 기준으로,  현재보다 이전 날짜의 span 은 그 날보다 가격이 같거나 작은날이 며칠인지를 이야기해주고 있으므로, 하루씩 back 할 필요 없이, 이 span 만큼 건너뛰어서 체크를 할수 있다. 물론 index outOfBound 는 피해야 한다. 처음 submit 할때는, 계산하는 함수를 따로 만들어서 뺐었는데, 그랬더니 32ms 가 나왔다. 가장 빠른 성능은 17ms 여서 뭔가 하고 봤는데 내 접근이랑 똑같은데 함수 호출만 없는거였다. 그래서 나도 private 함수로 뺀 부분을 그냥 합쳤더니 17ms 가 나왔다.  보통 이런 함수 호출이 성능에 그만큼 큰 영향을 주나 싶지만, 주어진 조건에 테스트케이스당 최대 만번의  호출을 하고, 전체 테스트케이스 합산시 15만번의 호출까지 한다고 하니. 함수스택 한번 들어갔다 나오는게 늘어나는만큼 유의미한 차이가 있긴 있었나보다. 그래봤자 15ms 가 일반적으로 쉽게 인식 가능한 범위는 아니지만. 아래의 calculateNewSpan 이 문제의 그 추가적인 함수 호출이었다. class StockSpanner { private int [] priceArray ; private int [] spanArray ; private int count ; public StockSpanner () { priceArray = new int [ 10000 ] ; spanArray = new int [ 10000 ] ; count = ...

한번에 풀지 못했고, intelliJ 를 통해 디버깅을 해야만 했다. 하지만 그렇게 해서라도 해결은 했다.  일단 첫번째 문제는,  정사각형 매트릭스에서 대각선은 전부 1 이기 때문에 대각선의 반쪽만 확인하면 될거라고 생각했는데, 맨 위 row 나 i맨 아래 row 같은 경우는, 맨 왼쪽 혹은 맨 오른쪽에서 시작해야만 자신의 connected node 를 가져올 수 있다.  그래서 0부터  iteration 을 도는데, visited 정보를 따로 관리 하지 않으면 이게 이미 빠진 건지 아닌지를 알 방법이 없다. 그래서 다시 무한루프에 걸렸었다.  visited 를 이용하니 해결. 성능은 좋지 않다.  4ms  였지만, 25% 일단 나의 접근은 set 에 전체 노드를 집어 넣어놓고 꺼내면서, 연관된 node 들을 다 꺼내는 priority queue 를 관리하는 것이었다. 그래서 기존의  set 이 empty 가 되면 종료. 일단 내 접근에서 문제점은, 쓸데없이 PQ 를 썼다는 것이다. 아무이유 없이. 그냥 Queue 를 썼어도 되었었다. 그리고 실제  node 들을 마치 당구공을 주머니에서 꺼내서 다른 주머니에 넣듯이 했는데. HashSet 으로 visit  을 관리할 필요가 전혀 없이, boolean[n] visited 만으로도 충분했다. 그래서 처음부터 각 node 를 Set 에 넣을 필요도, visited 를 set 에 넣을 필요도 없었다. DFS 로도 접근할 수 있는데, 이렇게 접근한 어떤이의 해결법은 다음과 같다. 아래 풀이를 보고 있자면 사실 그렇게 복잡할 필요도 없었겠다는 생각이 든다. public int findCircleNum ( int [][] isConnected) { boolean [] visited = new boolean [isConnected. length ] ; int provinces = 0 ; for ( int i = 0...

풀지 못했다. 가장 많은빈도수에 오른 문제임에도 불구하고. 처음 풀어보는 문제였는데. 못풀었다.  그동안 풀었던 문제는 사실 한번씩 풀어봤던 문제들이다. 그래서 쉬웠고, 그래서 한번에 통과도 하고 그랬던 것이다. 처음보는 문제는 또 이렇게 당황하고, 접근을 못한다. 각 알파벳의 처음과 마지막 index 를 찾아서, (a,b) 이런식으로 만들고,  겹치는 알파벳들은 merge  하면 될것 같았다. 하지만 그렇게 하면 merge  를 하더라도 문제에서 말하는 답을 return 하기엔 또 정렬을 하고, 계산을 해야한다. 생각해보니, 어떤 인도인에게 이 질문을 받은것 같기도 하다.그때. I said "infinite" 이라면서. infinite pool 에 알파벳들이 있는데. 하나씩 꺼낼수 있고, 이럴때 한번만 나타나도록 partition 을 구하라고 했었다.  그때도 못풀었고, 지금 역시,  infinite  가 아닌데도, 못풀었다. 비슷한 문제인지 조차도 한참 뒤에 알았다. 그때 당시엔 새로운 문제인줄 알았는데. 새로운 문제가 아니었다. 수많은 문제 은행 속 문제중에 내가 아직 안풀었던 것 뿐. 이미 2018년도에 누군가들이 풀었던 문제들이었던 거다. 나는 몰랐다가, 2019년 6월에 처음 그 문제를 인도인한테 접했고. 끝내 풀지 못한 내 풀이는 장황하고,  두서없고, 결론을 맺지 못했다. 그러나 역시 정답은 생각보다 간결하고 깔끔했다. 늘 그렇다. 각각의 알파벳 캐릭터의 가장 마지막 index 를 배열 26개에 관리한다.  그리고 for 를 toCharArray() 에 대해 돌면서 각 index 별로 그 캐릭터의 last index 를 가져와 last  라는 변수에 저장한다.  그리고 이렇게 유지한  last 와 현재 캐릭터의 last index 중 max 값을 last 에 계속 유지한다.  그래서, 현재 index  가 last ...

dfs 접근 법을 사용했고, number of islands 와 유사하나, 시작점의 색깔과 동일한 색깔만 바꾼다는 조건이 추가되어 있긴 하다. 오타, 대소문자를 꼼꼼히 살필것. int 를 init 으로 쓴다거나,  newColor 를 newcolor 로 써서 compile error  가 났다. 이를 제외하고는 한번에 accept. matrix 가 MxN  이라고 하면,  최악의 경우 모든 배열을 바꿔야하므로,  시간 복잡도는 O(MN)  이 된다.  간단한 문제여서 더 쓸건 없지만, 만약 BFS 로 접근해야 한다면 어떻게 해야할까?  자주 했었는데,  Queue 를 쓰면 된다. java 에서 Queue 구현은 LinkedList 로 되어 있다.  따라서 맨처음 주어진 포인트를 Queue 에 넣고, 뽑아서 체크하고, 4방향의 포인트들을 다시 queue 에 넣고. 이런식으로 해서 queue  가 텅 빌때까지 돌면 된다.  이 경우 queue 에 넣을 때 4방향 포인트를 다 넣을 필요 없이, 주어진 조건에 부합해서 색을 변경한 경우에만 넣으면 된다. 

첫번째에 accept 되었지만, map 을 다루는 과정에서 compile 에러가 나왔고,  (getOrDefault, put) map 에서 value 들을 가져올때는, map.getValues()  가  아니고  map.values()  였다. time complexity 는, string 개수를 N개라고 할 때 각 단어들에 대해 interate 돌기 때문에, O(N) string 각각의 길이를 k 라고 하면, 매 단어마다  char 로 쪼개서 정렬을 다시 했기 때문에 klogk가 든다. 따라서 O(Nklogk) 가 되는것 같다. anagram 으로 묶을때 같은 group 인지 체크하는 함수를, char array 로 바꿔서 정렬해서 확인하지 않고, 뭔가 다른방법으로 해야 성능을 높일 수 있을 것 같다.

며칠전 풀었던 문제와 비슷하게, closest K 가 조건인 만큼, PQ 를 이용하면  될것 같아서 접근했고, compile 에러 ( pq.size() 에서 () 빼먹음, cnt++;  에서 ; 빼먹음)  을 빼면 한번에 accept 되었다.  closest K 를 구하는 만큼, max heap 을 이용하는 것이 포인트 이다.  time complexity 는 PQ 에 point  개수 N 개 만큼 insert 했으므로, O(NlogN) 이 되는것 같다. 하지만 내 풀이는 28ms 로, 매우 오래 걸렸다.

IDE 의 도움을 받았지만 첫 시도에 accept 되었다. 성능은 좋지 않았다. 일단 words 를 iterate 하며 map 에 넣었고, 이후 pq 에 다시 넣었는데, 이때 pq 의 comparator 를 빈도수, 그다음 알파벳 순서로 지정하였다. 이후 pq 를 iterate 하며 string 을 list 에 넣어 return 하였다. PQ  선언할 때 PriorityQuene<>(n) 을 하면 아이템 개수를 n개 만큼만 허용하는 줄 알았는데, 그게 아니고 initial capacity 이다. 당연히 더 넣을수록 늘어난다.  나의 복잡도는, word 개수를 N 이라고 하면,  처음 hashmap put 할때 iterator O(N) pq 에 put  할때  O(NlogN) pq 에서 꺼내와서 list 에 넣을때 O(k) 해서 O(N)+O(NlogN)+O(k) 가 되는듯 하다. Trie  생각도 해봤는데, count 는 저장한다 쳐도, Top K 개를 어떻게 관리해서 꺼내올지를 몰라 접근하지 못했다.

전형적인 DFS  문제로, leetcode 에서 medium  로 되어 있으나, 다른 DFS 를 사용하는 문제들에 비하면 easy 인것 같다 풀어본적이 있고 유명한 문제여서 거의 한번에 pass는 했으나,  완전히 한번에 pass 하지 못했는데, 코드를 다 짠 뒤 compile  에러가 여기저기 있었다 [][] 배열 array 의 index 를 i, j 를 x, y 로 헷갈린다거나 배열 이름 오타 grid 를 gird  로 적었다거나 배열 index 예외 처리를  copy & paste 하느라 row, col 모두 x 에 대해 한다거나 예외 처리시 grid.length  보다 작아야 하는데 x == grid.length 에 대해 까먹었거나 하여 한번에 통과하지 못했다. 한번 본다고 코드를 다 짠 후 skim 하긴 했는데 위에걸 하나도 발견 못한건, 안한거나 마찬가지고 할 이유가 없는거나 마찬가지다. 정신 똑바로 차리고 꼼꼼히 봐야한다. Time Complexity nested loop 로 grid 의 행과 열에 대해 한번씩 visit 하므로 O(MN),  M = grid.length, N = grid[0].length 로 보인다. 속도가 느려 (2ms) 더 빠른 사람걸 봤는데 (0ms), 나머지는 똑같은데, 전체 grid 에 대해서 for를 돌면서 dfs 를 들어가지 않고, 하나를 찾았으면, 다음 island 시작점을 찾기 위해 grid 를 따로 iterate 한다. 그게 바로 아래의 findNext 함수이다.  매우 큰 array 이에, 매우 sparse 한 경우라면, 이렇게 하는것이 더 효율적일 수 있겠다. 매번 dfs 들어가서 edge 체크하는 불필요한 작업을 하지 않으니. public static int [] findNext ( char [][] grid, boolean [][] visited, int r, int c) { for ( int cc = c; cc...

해결은 했는데, 공간 복잡도 측면에서 매우 비효율적이었다. 주어진 두 list  의 pointer 들만 잘 바꿔줘도 되는걸, 복잡해서 새로운 node 를 매번 만들었기 때문이다.  아래의 iterative 가 원래 내가 풀고싶던 방식이고, recursive 도 풀기 전 접근 단계에서 생각은 했으나 구현은 못한 방식이다. LinkedList  유형의 문제를 풀때는,  sentinel node 를 하나 만들어서 return 을 쉽게 하는 것 node.next.next  식의 접근 방식도 유용하게 쓰이니 기억할 것 null 체크를 항상 주의 할것 *Iterative public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode ptr1 = l1; ListNode ptr2 = l2; ListNode sentinel = new ListNode(); ListNode ptr3 = sentinel; while (ptr1 != null && ptr2 != null ) { if (ptr1. val <= ptr2. val ) { ptr3. next = ptr1; ptr1 = ptr1. next ; } else { ptr3. next = ptr2; ptr2 = ptr2. next ; } ptr3. next . next = new ListNode(); ptr3 = ptr3. next ; } ptr3. next = (ptr1 == null ) ? ptr2 : ptr1; return sentinel. next ; } *Recursive public ListNode mergeTwoLists (ListNode l1, ListNode l2) { if (l1...

 Easy  이고, 예전에 풀어봤었고, tree 문제는 잘 파악만 하면 몇줄 안에 해결되는 문제여서 좀 만만하게 생각하고 풀었는데. 대실패.  논리적으로 생각하기보다, 풀었던 기억을 되살리려 했다. Tree 문제의 경우, signature 로 주어진 함수를 자식 node 로 recursive 하게 호출하면 해결되는 문제들을 많이 봐서, 그런식으로 접근하려고 했는데 다양한 edge case  에 번번히 실패 그리고 결국 실행이 되긴 했는데 LTE 떠서 실패 recursive 하게 호출 하려면, 그 함수가 정확히 뭘 하는지 구분 해야한다. 이번 문제에선 recursive 하게 호출하되,  두 TreeNode 가 정확히 matching 되는지 체크하는 함수는 또 따로 recursive 로 돌리는것이 관건이었다. 말하자면 2개의 recursiv 함수가 있는 것이다.  null 체크를 제외한 주요 호출은 아래처럼 된다.  public boolean isSubtree (TreeNode s, TreeNode t) { return exactSame (s, t) || isSubtree (s. left , t) || isSubtree (s. right , t); } private boolean exactSame (TreeNode s, TreeNode t){ if (s. val ==t. val ){ return exactSame (s. left , t. left ) && exactSame (s. right , t. right ); } return false ; } Complexity tree s  의 node 개수를 S, tree t 의 node 개수를 T  라 한다면, 각각의 s 의 노드를 root 로 하는 subtree가 tree t 와 exactly matching 하는지 확인 하므로,  최악의 경우 O(ST) 가 되는것 같 다....

 String 을 sanitize 하는 부분에서 애를 먹었다. Map traverse 방법은 물론이고 그게 최적인지 잘 모르겠다.  *Trial and Error sanitize 를 하면서 특수문자를 ""로 바꿨더니 "a,b"  가 "ab" 가 되어버렸다.   trim 하는것을 까먹어,  "cat" 과 "cat " 이 각각 다른 단어가 되어버렸다. "" 가 하나의 단어가 되었다. isEmpty 로 걸렀어야했다. *Complexity Paragraph 의 length 를 l 이라고 하고,  banned 의 size 를 s  라고 하면. set 에 ban 넣는 O(s) 특수문자 sanitize 하는데 O(l) split 하는데 O(l) split  한 단어의 개수를 n 이라 하면, HashMap 에 넣으니까, average O(1), worst O(n) HashMap traverse 한번 하니까 O(n) 다 더하면  O(s)+2O(l)+O(1)/O(n)+O(n) 이다. average : O(s)+2O(l)+O(1)+O(n) = O(s)+O(l)+O(n) worst : O(s)+2O(l)+O(n)+O(n) = O(s)+O(l)+O(n) 결국 O(s+l+n) 의 linear 한 complexity 를 갖는것 같다.  처음 문제를 보고 접근법을 생각할 때, 이를 Trie 를 통해 접근하면 Paragraph 를 한번만 읽으면 되지 않을까 생각했는데, Trie 구현을 안찾아보고 하기 어려워서 그냥 Map 으로 했다. 가장 성능이 좋은 알고리즘을 보니 역시 Trie 로 접근했다. Trie 를 익숙하게 다룰 줄 알아야겠다. 

 이 문제는 stack 으로 푸는게 먼저 있었는데, 답을 보다 보니 divide conquer 가 더 이해가 잘되고 직관적이다. 아래와 같이, 우선 가장 높이가 작은 인덱스 i를 찾는다. 그 다음,  그것을 기준으로 왼쪽과 오른쪽으로 쪼갠다. 그리고 쪼개진 왼쪽 파트에서 나올 수 있는 가장 큰 값, 오른쪽 파트에서 나올 수 있는 가장 큰 값, i 를 포함한 넓이, 이렇게 3가지중 max 값을 구한다. 각각의 왼쪽 파트와 오른쪽 파트는 또 다시 재귀적으로 들어가서 가장 높이가 낮은 인덱스를 각각 구하고.. 또 쪼개고..       public int largestRectangleArea(int[] heights) { return calculateArea(heights, 0, heights.length - 1); } public int calculateArea(int[] heights, int start, int end) { if (start > end) return 0; int minindex = start; for (int i = start; i <= end; i++) if (heights[minindex] > heights[i]) minindex = i; return Math.max( heights[minindex] * (end - start + 1), Math.max( calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end) ) ); } 구현상 포인트는 divid...