알고리즘 공부/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이 만들어진다.

 

 

 

 

 

코드

 

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;
}
};

 

반응형