알고리즘 공부/LeetCode
[LeetCode] 2871. Split Array Into Maximum Number of Subarrays (C++)
EVEerNew
2023. 10. 10. 18:28
반응형
문제
https://leetcode.com/problems/split-array-into-maximum-number-of-subarrays/description/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
풀이
난이도: Medium
SubArr는 연속이어야 했기때문에 쉬운 문제였다.
A subarray is a contiguous part of an array.
SubArr들의 Score Sum이 최소가 될려면, 분리할 SubArr는 반드시 score 0을 만들어야 한다.
분리없이 Score가 0이였는데, 분리된 subArr에서 Score가 1이라도 만들어진다면, 0 +1로 최소 sum을 만족하지 못한다.
따라서 연속된 배열을 AND 연산을 해보면서, 0이된다면 subArr(start~end)로 분리시킬때 subArr를 최대한 만들 수 있다.
만약 남겨진 배열로는 0을 만들지 못하면 0을 만든 이전 subArr와 합치면 0이 만들어진다.
코드
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
//각 수가 최대 10^6을 나타낼 수 있으므로 2^20 범위까지 1로 채움 | |
int makeAllBitOneNum() { | |
int ret = 1; | |
int move_bit = 1; | |
for (int i= 1; i<=21; ++i) { | |
ret |= (move_bit << i); | |
} | |
return ret; | |
} | |
int maxSubarrays(vector<int>& nums) { | |
const int allOneBits = makeAllBitOneNum(); | |
int conti_bits = allOneBits; | |
int subArr_num = 0; | |
for (int i = 0; i< nums.size(); ++i) { | |
conti_bits &= nums[i]; | |
if (!conti_bits) { //AND로 0이 만들어진 경우 arr 분리 | |
++subArr_num; | |
conti_bits = allOneBits; | |
} | |
} | |
if (subArr_num == 0) //AND가 0으로 만들지 못하는 경우 | |
return 1; | |
return subArr_num; | |
} | |
}; |
반응형