[ leetcode ] 1493. Longest Subarray of 1's After Deleting One Element

0과 1로만 이루어진 배열에서 한 가지 원소를 제거하였을 때, 1로만 이루어진 가장 긴 subarry의 길이를 반환하는 문제.

 

array를 순회하면서 나올 수 있는 경우의 수를 생각해보면 다음과 같습니다.

 

[0] 1을 만난다면 현재 len을 증가시켜 줍니다. len++, zero_count = 0;

[1] 0을 만나기 전 1이 없었다면 정답과 관련된 길이를 구할 수 없습니다. zero_coun++;

[2] 0을 만나기 전 1이 있었고, 0을 만난게 처음이라면 정답과 관련된 길이를 해당 길이는 과거형이 됩니다.

     prev_len = len, len = 0;

[3] 0을 두 번 만났다면 prev_len과 len모두 0이됩니다.

 

이렇게 해서 결국 prev_len + len의 길이가 가장 긴 경우가 정답이 됩니다.

순회 후 answer가 변경되었다면, 마지막이 1로 끝났을 수 있으로 다시 prev_len + len과 현재 answer를 비교

순회 후 prev_len과 len이 모두 0이면 모두 0으로 이뤄진 array입니다.

순회 후 prev_len은 0이지만 len은 숫자가 있고, len이 array길이와 같다면 모두 1로 이뤄져있고, 아니라면 len을 반환

 

위를 충족하는 코드는 다음과 같습니다.

#define max(a,b)((a) > (b) ? (a) : (b))

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int answer = 0;
        int len = 0, prev_len = 0, zero_count = 0;
        for (int i = 0; i < nums.size(); i++) {
        	if (nums[i]) {
                len++;
                zero_count = 0;
                continue;
            }
        
            zero_count++;

            if (len && zero_count == 1) {
                answer = max(answer, prev_len + len);
                prev_len = len;
                len = 0;
            }
            else if (zero_count == 2) {
                prev_len = len = 0;
            }
    	}
        if (answer) {
            answer = max(answer, prev_len + len);
            return answer;
        }
        if (!prev_len && !len) return 0;
        return len == nums.size() ? len - 1 : len;
    }
};