본문 바로가기

알고리즘 문제/Leetcode283

[leetcode] 1052. Grumpy Bookstore Owner 문제 : https://leetcode.com/problems/grumpy-bookstore-owner/ 슬라이딩 윈도우로 풀었다. grumpy가 0인 경우는 X 타임과 상관없이 항상 일정하다. -> 미리 저장. (변하지 않는 값) grumpy가 1인 경우는 X타임에 따라 달라진다. -> 슬라이딩 윈도우로 최대가 되는 값을 구한다. (변하는 값) customers를 앞에서부터 탐색하면서 슬라이딩 윈도우 범위내에 grumpy가 1인 custmoers 배열 요소의 합을 구한다. 구한 합의 최대 값과 gumpy가 0일 때의 customers 배열의 합을 더한 값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/1e7dff3e4b90c1d88e7b60.. 2019. 6. 15.
[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.

티스토리툴바