알고리즘 문제/Leetcode283 [leetcode][1009] Complement of Base 10 Integer 문제 : https://leetcode.com/problems/complement-of-base-10-integer/ 6 - 0 3 - 1 1 - 1 0 - 1 N을 6이라 했을 때, 2진수는 1110이다. 따라서 보수는 0001이 된다. N을 2로 나눈 나머지 값이 0이면 1을 1이면 0을 해당 자리 수 값에 곱해서 정답에 더한다. N이 0인 경우 보수는 1이므로 이 때는 예외처리했다. 시간 복잡도는 O(logN). + N = 5(101) 일 때, 1의 보수를 구해보자. 1000 - 101 = 011 011 - 1 = 010 2진수의 비트수는 log2(N)으로 구할 수 있다. 예를 들어 N = 5(101) 일 때, log2(5) = 2.32193. 이에 +1을 한 뒤 정수로 바꿔주면 3이 된다. 이제 .. 2019. 3. 17. [leetcode][1005] Maximize Sum Of Array After K Negations 문제 : https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/ 배열을 오름차순 정렬한다.음수이고 K가 양수이면 -1을 곱해서 sum을 더한다(K도 1씩 감소). 그러면서 마지막으로 -1을 곱한 수를 따로 저장해둔다.양수이고 K가 양수이면 K를 2로 나눈 나머지를 구한다. 나머지가 1이라면 양수에 -1을 곱해야 하는데 이때, 마지막으로 -1을 곱한 음수와 비교해야 한다.예를 들어, [-8,-5,-3,-5,-2,3] 이고 K가 6일 때, 마지막으로 -1을 곱한 음수는 -2이고. -1을 곱할 양수를 3이라고 하자.총합은 가장 작은 양수인 3을 음수로 만드는 것보다 -2를 양수로 만드는 것이 더 크다.그러므로 -2는 양수로 만들지 않고 3.. 2019. 3. 16. [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][997] Find the Town Judge 문제 : https://leetcode.com/problems/find-the-town-judge/ 다른 사람한테 믿음을 받은 횟수(?)를 저장한는 배열(cnt라고 하자)을 하나 만든다.trust 배열을 탐색하며 해당 배열을 갱신한다.조건에서 판사는 아무도 믿지 않으므로 다른 사람을 믿는다고 한 사람의 횟수는 -N으로 초기화한다. (절대 정답이 될 수 없게)trust 배열을 탐색하며 cnt 배열을 갱신했으면 cnt 배열을 탐색하면서 요소 값이 N-1인(자기를 제외한 모든 사람의 수) 인덱스가 정답이 될 수 있다.만약 가능한 인덱스가 2번 이상 나오면 정답이 될 수 있는 경우는 유일하다고 했으므로 -1을 반환하고 1번 나오면 그 사람 번호를 반환한다. 시간 복잡도는 O(|trust| + N). 소스코드 :.. 2019. 3. 2. 이전 1 ··· 38 39 40 41 42 43 44 ··· 48 다음