subsum11 [Leetcode] 2439. Minimize Maximum of Array 문제 : https://leetcode.com/problems/minimize-maximum-of-array/description/ 0부터 인덱싱된 n개의 음이 아닌 정수로 구성된 nums 배열이 제공됩니다. 한 번의 작업에서는 다음을 수행해야 합니다. 1. 1 0 입니다. 2. nums[i]를 1 감소시킵니다. 3. nums[i-1]를 1 증가시킵니다. 작업 수행 후 nums의 최대 정수 값 중 가능한 최소 값을 반환합니다. nums의 최대 정수 값 중 가능한 최소 값을 구하려면 모든 요소들을 평균 값으로 만들면 됩니다. 문제 2, 3번을 통해 알 수 있는 점은 뒤에 있는 nums 요소의 수는 앞으로 이동 가능할 수 있다. 입니다. ex) [1, 2, 3, 4] -> [3, 2, 3, 2] (4의 2를.. 2023. 4. 5. [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. 이전 1 2 다음
