[leetcode] Max Consecutive Ones II

https://leetcode.com/explore/featured/card/fun-with-arrays/523/conclusion/3230/

Explore - LeetCode

-> Fail 

 

0과 1로 이루어진 특정 배열이 주어졌을때, 최대 한개의 0을 뒤짚을 수 있는 경우 연속되는 1의 개수가 가장 긴 값을 구하는 문제이다. 

 

1. Brute Force 방식으로 풀기 

 

모든 연속된 시퀀스를 찾기위해 이중 for문을 사용하여 탐색한다.

0 의 개수를 체크 한 후 0이 한개 이하라면, 현재 원소의 길이를 구하여 기존의 길이보다 긴 값인지를 확인하여 계속해서 긴 값으로 유지시키며 최종적으로 가장 긴 값을 리턴한다. 

 

시간복잡도는 O(n2) 으로 좋은 방법은 아니다. (간혹 타임아웃이 발생하기도 한다.)

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.length; left++) {
            int numZeroes = 0;

            // check every consecutive sequence
            for (int right = left; right < nums.length; right++) {
                // count how many 0's
                if (nums[right] == 0) {
                    numZeroes += 1;
                }
                // # update answer if it's valid
                if (numZeroes <= 1) {
                    longestSequence = Math.max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

 

2. Sliding Window 방식으로 풀기

 

Sliding Window 란?

ㄴ 특정 배열이 주어졌을때 고정된 일정 범위 안에서 정보를 유출하고 이를 비교할때 사용되는 방법이다.

ㄴ N개의 원소를 갖는 배열과 W의 넓이를 갖는 창문이 있다고 가정했을때, 창문을 왼쪽부터 시작하여 한칸씩 오른쪽으로 이동하며 매 순간 창문 안에서의 정보 유출을 할 수 있다. 

 

예를들면, 원소가 8개인 배열과 넓이가 3인 창문이 있고 이 창문을 한칸씩 오른쪽으로 이동하는데 매 순간 창문 안에서의 합을 구해야 한다면 아래와 같은 방식으로 나타낼 수 있다.

[ 7, 2, 4, 1, 6, 5, 8, 3] 
7, 2, 4 -> 13

2, 4, 1 -> 7

4, 1, 6 -> 11

1, 6, 5 -> 12

6, 5, 8 -> 19

5, 8, 3 -> 16 

 

투 포인터 방식과 비슷하지만 고정 사이즈 윈도우를 사용하는 경우나 정렬 여부와 관계 없이 활용해야할 땐 슬라이딩 윈도우를 사용한다.

 

위 방식으로 Max Consecutive Ones II 문제를 풀어보자. 

 

반복문은 right을 기준으로 돌며, 인덱스의 값이 0이 나올때마다 체크를 한다. 

0이 두번 발견되면 left 을 이동시켜야하는데 left 의 값이 0이 나올때까지 증가시키며 0이 나오면 0을 체크하는 값을 다시 유효한 값으로 만들어준다.

 

이러한 과정을 반복하여 연속된 길이중 가장 긴 값을 리턴하는 방식이다. 

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int longestSequence = 0;
        int left = 0;
        int right = 0;
        int numZeroes = 0;

        // while our window is in bounds
        while (right < nums.length) {

            // add the right most element into our window
            if (nums[right] == 0) {
                numZeroes++;
            }

            // if our window is invalid, contract our window
            while (numZeroes == 2) {
                if (nums[left] == 0) {
                    numZeroes--;
                }
                left++;
            }

            // update our longest sequence answer
            longestSequence = Math.max(longestSequence, right - left + 1);

            // expand our window
            right++;
        }
        return longestSequence;
    }
}