본문 바로가기

subsum10

[Leetcode] 1658. Minimum Operations to Reduce X to Zero 문제 : https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/ 정수 배열 nums와 정수 x가 입력으로 주어진다. 한 번의 작업으로 배열 nums에서 가장 좌측 혹은 가장 우측에 있는 요소를 제거 하고 x에서 제거한 요소의 값을 뺄 수 있다. 최소 몇 번의 작업으로 x를 정확히 0으로 만들 수 있는지 구하라. 만일 불가능하다면 -1을 반환하라. 부분합과 투포인터로 구할 수 있다. 부분합을 만들어 subsum 배열에 세팅한다. 첫 번째 예제 [1, 1, 4, 2, 3], x=5 로 표를 세팅해보면 [그림1]과 같다. 정답이 되는 제거되는 요소는 가장 뒤 요소 2, 3이다. 이를 반대로 생각하면 제거되지 않는 요소들의 합은 nums 전체.. 2022. 6. 11.
[Leetcode] 731. My Calendar II 문제 : https://leetcode.com/problems/my-calendar-ii/ 부분합 문제. 정렬된 map을 만들고 map[start] + 1, map[end] -1을 갱신한다. ex) [[10, 20], [50, 60]] i 10 20 50 60 map[i] 1 -1 1 -1 부분합 1 0 1 0 map을 처음부터 탐색하면서 map[i]의 부분합을 구한다. 합을 구하면서 만약 3 이상인 경우가 있으면 map[start], map[end]를 이전 값으로 갱신한뒤 false를 반환한다. 탐색이 끝날때까지 3이상인 경우가 없으면 추가가 가능한 경우이므로 true를 반환한다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/med.. 2022. 4. 12.
[leetcode] 1094. Car Pooling 문제 : https://leetcode.com/problems/car-pooling/ 총 좌석이 capacity인 차량이 있다. 차량엔 capacity 만큼의 탑승자만 태울 수 있다. 차량은 동쪽으로만 주행하며 (탑승자 수, from, to) 정보를 저장한 trip 배열이 주어진다. from에서 탑승자 수 만큼 차량에 태우고 to에 탑승자 수 만큼 차량에서 내린다. capacity를 넘지 않게 모든 trip 여행들을 탐색할 수 있으면 true 아니면 false를 반환하라. 부분합 배열을 만들어서 풀 수 있다. to의 최대값이 1000이므로 1000 크기의 passenger 배열을 만든다. trips 배열을 탐색하며 passenger[from] 에는 탑승자 수 만큼 더하고, passenger[to]에는 탑.. 2022. 1. 7.
[Leetcode][1074] Number of Submatrices That Sum to Target 문제 : leetcode.com/problems/number-of-submatrices-that-sum-to-target/ 2차원 배열 matrix와 target 정수가 주어진다. matrix[x][y] (x1 2021. 4. 18.
[programmers][2021카카오공채] 광고 삽입 문제 : programmers.co.kr/learn/courses/30/lessons/72414 부분합 문제. hh:mm:ss 로 이루어진 문자열 시간으로는 계산하기 힘드므로 플레이타임, 광고시간, log 시간들 모두 second로 변환한 후 계산한다. log의 시작 시간을 start, 종료 시간을 end라 한다면 subSum[start]++, subSum[end]-- 로 갱신한다. 예를 들어, start가 1, end가 3이라면 index (i) 0 1 2 3 4 subSum[i] 0 1 0 -1 0 모든 log 정보를 탐색하며 subSum을 갱신했다면 처음부터 모든 subSum을 탐색하며 subSum[i] = subSum[i] + subSum[i-1]로 정보를 갱신한다. 갱신하면 특정 시간대의 광고를.. 2021. 3. 24.
[leetcode][1277] Count Square Submatrices with All Ones 문제 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/ 1과 0으로 이루어진 N x M 배열이 주어지면 1로 이루어진 정사각형의 개수를 구하라. 행, 열 subsum을 구한 뒤 이를 이용하여 구했다. 입력배열이 위와 같으면 행, 열 부분합 배열은 각각 위와같이 만들어진다. (2,1) 한 칸이 정사각형인지 판단하는 방법은 행 부분합에서 (2, 1) - (1,1) 값과 열 부분합에서 (2,1) - (2,0) 값이 둘 다 1이어야 한다. 즉, (2,1) 값이 1인지 확인하기만 하면 된다. 그 다음 (2,1)을 정사각형의 왼쪽 모서리로 두고 사이즈가 2인 정사각형이 가능한지 판단해보자. 이전 단계에서 (2, 1)은 모두 1인 것을 판.. 2020. 5. 23.

티스토리툴바