Medium174 [leetcode][1008] Construct Binary Search Tree from Preorder Traversal 문제 : https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/ 문제에서는 inorder 순서로 숫자 배열을 입력으로 준다고는 하지만 생각해보면 이진 탐색트리(BST)를 만드는 것과 같다.항상 루트부터 탐색하면서 NULL이 나올 때까지 현재 탐색중인 노드보다 작으면 왼쪽 자식, 크면 오른쪽 자식 노드로 탐색해간다.NULL이면 그 자리에 값을 val로 노드를 만들어 넣으면 된다.이렇게 하면 O(NlogN) 정도 나온다. (코드는 이 방식으로 짰다.)사실 입력 값을 다 알고 있으면 굳이 항상 루트 노드부터 탐색하면서 트리를 만들 필요는 없다.예를 들어 [8,5,1,7,10,12]가 입력값이라고 하자.inorder이.. 2019. 3. 13. [leetcode][998] Maximum Binary Tree II 문제 : https://leetcode.com/problems/maximum-binary-tree-ii/ 이 문제를 해결하려면 먼저 [654] Maximum Binary Tree 문제를 알아야 한다.654번 문제에서 조건은 배열을 입력받아 최대 값을 가진 노드를 기준으로 왼쪽 subarray는 왼쪽 자식 트리로, 오른쪽 subarray는 오른쪽 자식 트리로 만든다. 즉, 새롭게 추가되는 값은 왼쪽 자식 트리에 들어갈 수 없고, 오른쪽 자식트리에 속하거나 새로운 루트가 되는 경우 2가지 뿐이다. 따라서 알고리즘은, 1. root가 NULL인 경우 val로 node를 생성해서 반환. (새로운 루트 노드)2. root의 val보다 입력받은 val이 큰 경우 val로 node를 생성한 후 왼쪽 자식에 루트 노드.. 2019. 3. 10. [leetcode][1004] Max Consecutive Ones III 문제 : https://leetcode.com/problems/max-consecutive-ones-iii/ 투 포인터로 풀었다.큐를 하나 만들어서 0인 경우 0일 때의 인덱스를 큐에 저장한다.그리고 start, end 인덱스 2개를 저장한다. A 배열을 앞에서 탐색하면서 탐색 중인 인덱스가 end인덱스가 되는 정답이 될 수 있는 가능한 start 인덱스를 갱신해나간다.start인덱스는 0부터 시작되며 갱신되는 경우는 [start, end] 범위에 0의 개수(0 인덱스를 저장하는 큐의 size)가 K개를 초과하는 경우이다.start는 큐의 가장 앞에 있는 0의 인덱스 + 1이 된다.A 배열을 모두 탐색하면서 가능한 [start, end] 범위를 구하고 해당 범위의 길이 중 최대 값이 정답이 된다.시간복잡.. 2019. 3. 4. [leetcode][991] Broken Calculator 문제 : https://leetcode.com/problems/broken-calculator/ X를 Y로 만드는 횟수가 아닌 반대로 Y를 X로 만드는 횟수를 구했다.반대로 구했기 때문에 연산도 반대가 된다. (/2, +1) 만약 X가 Y보다 크다면 나누기 2를 하면 안된다. 따라서 +1 연산만하게 되고 +1 연산 횟수는 X - Y가 된다.X가 Y보다 작고 Y가 2의 배수라면 /2 연산을 한다.X가 Y보다 작고 Y가 2의 배수가 아니라면 +1 연산을 한다. 소스코드 : https://gist.github.com/fpdjsns/c4b613504108f095f368c875dbadeda7 2019. 2. 13. [leetcode][990] Satisfiability of Equality 문제 : https://leetcode.com/problems/satisfiability-of-equality-equations/ Union-Find로 풀었다.먼저 == 인 경우만 보고 Union-Find로 같아야 하는 알파벳들끼리 그룹으로 묶는다.다음으로 같지 않아야 하는 조건(!=)을 보고 알파벳 두 개의 그룹이 다른지 판단한다. 만약 달라야하는 알파벳 두 개가 서로 같은 그룹이라면 조건이 충돌나므로 false를 반환한다. 소스코드 : https://gist.github.com/fpdjsns/e8e25e4cd52a20322f91556fee3e7994 2019. 2. 11. [leetcode][988] Smallest String Starting From Leaf 문제 : https://leetcode.com/problems/smallest-string-starting-from-leaf/ DFS로 완전탐색해서 풀었다. 루트를 기준으로 자식 노드로 탐색하면서 문자열을 만들어간다.현재 노드의 val를 이때까지 만든 문자열 앞에 붙인다.그리고 리프 노드가 되면 이때까지 만든 문자열을 이때까지 구한 정답 문자열과 비교해서 사전순으로 앞서있다면 정답을 갱신한다. 시간복잡도는 모든 노드를 탐색해야 하므로 O(N + 정답문자열 비교 시간 * 리프노드 개수) 이다.완전이진트리라 했을 때 정답문자열 비교 시간 * 리프노드 개수는 트리의 높이는 logN이므로 정답 문자열 비교 시간은 logN이고 리프노드 개수는 N/2이므로 N*logN/2가 된다.좀 더 상세하게 따지면 몇가지 케이.. 2019. 2. 9. 이전 1 ··· 23 24 25 26 27 28 29 다음