본문 바로가기

알고리즘 문제408

[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] 1020. Number of Enclaves 문제 : https://leetcode.com/problems/number-of-enclaves/ DFS 문제. 배열 A를 탐색하면서 1일 때 현재 요소를 기준으로 상하좌우로 탐색(DFS)하면서 1의 개수를 센다. 세면서 방문한 배열 요소는 0으로 갱신한다. 만약 DFS 탐색시 배열밖으로 벗어난다면 1의 개수는 정답이 될 수 있으므로 정답에 더해준다. 소스코드 : https://gist.github.com/fpdjsns/91d296e10a828da48b4751a9fad00080 2019. 4. 8.
[leetcode][1021] Best Sightseeing Pair 문제 : https://leetcode.com/problems/best-sightseeing-pair/ 투포인터로 풀었다. 배열 A를 1 인덱스부터 탐색하면서 탐색 중인 원소를 j 인덱스로 본다. A[i] + A[j] + i - j의 최대값이 정답이다. i 인덱스는 A[i] 2019. 3. 29.
[leetcode][1014] Capacity To Ship Packages Within D Days 문제 : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ 이분탐색으로 풀었다.l = weights 배열중 가장 작은 수. r = weights 배열의 합.정답이 될 수 있는 값의 제일 작은 값(l), 제일 큰 값(r)을 구하고 l을 증가, r을 감소 시키면서 정답이 될 수 있는 가장 작은 수를 구한다.l과 r의 중간값을 구한다음, 구한 중간 값으로 weights 배열을 탐색하면서 소요되는 day를 직접 구해본다.구한 day가 D보다 작거나 같다면 정답이 될 수 있는 경우이므로 r을 중간값으로 갱신한다음 다시 반복한다.day가 D보다 크다면 정답이 될 수 없으므로 l을 중간값+1으로 갱신 후 다시 반복한다.이를 l이 r보다 크거.. 2019. 3. 22.
[leetcode][1013] Pairs of Songs With Total Durations Divisible by 60 문제 : https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/ map을 이용했다.[30, 20, 150, 100, 40, 60, 60] 이 입력이 주어졌으면 이를 60으로 나눈 값들의 개수를 map에 저장한다. key = 60으로 나눈 나머지. value = 개수즉, 위 예제에서는 [30, 20, 30, 40, 40, 0, 0]을 key, value형태에 맞춰 넣으면{0, 2}, {20, 1}, {30, 2}, {40, 2}가 map에 들어간다.짝이 될 수 있는 것은 20 - 40. 30 쌍이다. 0 쌍의 개수는 2 * 1 = 2. 20 - 40 쌍의 개수는 1 * 2 = 2.30 쌍의 개수는 2 * 1 = 2.. 2019. 3. 17.
[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.

티스토리툴바