HARD56 [leetcode][719] Find K-th Smallest Pair Distance 문제 : https://leetcode.com/problems/find-k-th-smallest-pair-distance/ 모든 요소들의 pair들의 최소 차 중 k 번째가 되는 수를 구하는 문제. 이진탐색으로 정답이 되는 범위를 줄여나가면서 찾는다. 여기서 low, high, mid는 단순히 nums 배열의 인덱스가 아닌 pair의 차이가 된다. 즉, low = 정답이 가능한 범위의 pair 최소 차이 high = 정답 범위의 pair 최대 차이 mid = 범위를 줄이기 위해 몇 번째 최소 차인지 비교하기 위한 수. 가 된다. nums를 오름차순으로 정렬한다. low = 0, high = 최대값 - 최소값으로 세팅한다. low를 nums를 한 번 탐색하면서 nums[i+1] - nums[i] 중 최소값.. 2019. 12. 21. [leetcode][140] Word Break II 문제 : https://leetcode.com/problems/word-break-ii/ DFS를 돌리면 TLE가 발생해서 memoization을 추가했다. dp[lastInd] = s[0 ~ lastInd] 로 만들 수 있는 정답 가능 문자열의 리스트이다. 즉 우리가 구할 건 dp[ |str| - 1 ]. 문자열의 뒤에서부터 탐색을 하므로 wordDict의 문자열들의 마지막 문자를 key로 하는 dictionary를 하나 만들었다. ex) wordDict = ["ab", "b", "ac"] -> dict ={ {'b', ["ab", "b"]}, {'c', ["c"]}} dict에서 lastInd를 key로 하는 단어들을 가져온 뒤, 문자열의 서브 문자열이 가능한지 체크한다. ex) banana a가 l.. 2019. 12. 19. [leetcode][1192] Critical Connections in a Network 문제 : https://leetcode.com/problems/critical-connections-in-a-network/ tarjan 알고리즘으로 풀었다. dfs로 정점들을 방문하면서 해당 정점을 방문한 순번(num)과 하나의 간선만으로 갈 수 있는 정점들 중 가장 작은 정점(low)을 저장하는 배열들을 저장한다. low 저장하는 조건. now = 현재 탐색중인 정점 next = now에서 방문할 다음 정점 1. next 정점을 이미 방문한 경우(back edge) : low[now] = min(low[now], low[next]) 2. next 정점을 아직 방문하지 않은 경우 : low[now] = min(low[now], num[next]). 2번인 경우 next 정점을 dfs로 방문하면서 low.. 2019. 9. 23. [leetcode] 1172. Dinner Plate Stacks 문제 : https://leetcode.com/problems/dinner-plate-stacks/ let) capacity = 2 index 0 1 2 3 stack 4 1 3 5 fullStack : 가득찬 스택 인덱스 (2) blankFullStack : fullStack 사이사이의 index (0, 1, 3(3인덱스 스택이 가득찼다가 삭제된 경우)) stackMap : key - index, value - stack ({0, {1}}, {2, {4,3}}, {3, {5}) push 처음 push하는 경우는 0번 인덱스 stack에 push. 가득찬 스택들 중간에 빈 곳이 있는 경우(blankFullStack이 있는 경우) 빈 곳 중 가장 왼쪽에 넣어준다. 왼쪽부터 차례대로 스택들이 모두 차있는 경.. 2019. 8. 30. [leetcode] 1028. Recover a Tree From Preorder Traversal 문제 : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/ 탐색은 preorder로 왼쪽을 다채우고 부모노드로 올라가고 나서는 값을 채우기 위해 왼쪽 자식트리로 내려가지 않는다. TreeNode 구조체는 자식 노드의 정보만 담고 있으므로 부모노드를 저장하는 스택을 하나 만들었다. pair getValAndDepth(string& s) { if (s.size() == 0)return { -1, -1 }; int ind = 0; int val = 0; int depth = 0; for (; ind 0) { ind--; break; } else depth++; } else { val *= 10; val += s[ind] - '0'; }.. 2019. 4. 20. [leetcode][992] Subarrays with K Different Integers 문제 : https://leetcode.com/problems/subarrays-with-k-different-integers/ 투포인터로 풀었다.A = 2212211이고 K가 2일 때를 예로 들어보자.인덱스 r이 1일 때,인덱스 l은 K가 2일때를 만족하는 인덱스 0부터 시작한다.이 때, 인덱스 r을 포함시키는 정답이 될 수 있는 경우의 수를 구한다.인덱스 0부터 A[i]의 개수가 1개일 때까지 l을 증가시킨다.정답이 될 수 있는 경우는 이 때 인덱스 l의 증가량 +1이 된다. 정답이 될 수 있으려면 최소한 1개의 범위 내에 각 숫자를 최소한 한 개는 가지고 있어야 한다.즉, 인덱스 r을 포함한 정답가능한 최소 문자열은 위 그림과 같이 "2 1" 이다.여기에서 K가 2일 때를 만족하는 범위의 인덱스들을.. 2019. 2. 14. 이전 1 ··· 6 7 8 9 10 다음
