LeetCode - 3208. Alternating Groups II

문제링크

 

문제 설명

빨간색과 파란색 타일로 이루어진 원형 배열이 있습니다.

정수 배열 colors와 정수 k가 주어집니다. 각 타일의 색상은 colors[i]로 표현됩니다:

• colors[i] == 0이면 i번째 타일은 빨간색입니다.
• colors[i] == 1이면 i번째 타일은 파란색입니다.

교차 그룹(Alternating Group)은 원에서 연속된 k개의 타일로 이루어진 부분이며, 서로 교차하는 색상을 가져야 합니다.
즉, 그룹의 첫 번째와 마지막 타일을 제외한 모든 타일은 양옆의 타일과 다른 색상을 가져야 합니다.

원형 배열이므로, 첫 번째 타일과 마지막 타일도 서로 인접한 것으로 간주합니다.

k개의 연속된 타일이 조건을 만족하는 교차 그룹의 개수를 반환하세요.

제한 사항

• 3 <= colors.length <= 10^5
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

예시

Example 1:

Input: colors = [0,1,0,1,0], k = 3

Output: 3

Explanation:

Alternating groups:

Example 2:

Input: colors = [0,1,0,0,1,0,1], k = 6

Output: 2

Explanation:

Alternating groups:

Example 3:

Input: colors = [1,1,0,1], k = 4

Output: 0

Explanation:

풀이 흐름

• colors.length의 범위가 10^5 이므로 하나씩 일일이 확인하면 시간 초과가 발생합니다.
• 고민하다가 떠오른 방법은 교차 그룹을 일일이 구하지 말고 교차가 이뤄지는 횟수를 센 뒤에 교차의 횟수가 k 이상이면 교차 그룹의 갯수를 1씩 카운트하면 되지 않을까 생각했습니다. (시간복잡도: O(N))
• 원형 배열이므로 colors.length의 2배를 돌면서 교차가 이뤄지는 횟수를 세주고 만약 교차되지 않으면 교차의 횟수를 다시 1로 초기화해줍니다.

코드

import java.util.*;

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        int c = 0;
        int re = 0;
        for (int i = 0; i < 2 * n; i++) {
            if (colors[i % n] != colors[(i + 1) % n]) {
                c++;
            } else {
                c = 1;
            }
            if (i >= n && c >= k) {
                re++;
            }
        }
        return re;
    }
}