[LeetCode] 3208. Alternating Groups II (Python)

Problem

 

Solution

sliding window

 

처음에 구현으로 2중 포문 돌렸다가 time limit exceeded 났던 문제.

이 문제도 똑같이 sliding window 기법으로 풀어야된다.

원형 배열이라서 colors[: k-1]개만큼 기존 배열에 더해준다.

그리고 이전 원소와 값을 비교하며 (index 범위는 1 부터 시작) count 를 증가한다.

count가 k 이상이면 조건을 만족하므로 answer ++

만족하지않으면 count = 1 로 초기화하여 다시 리셋해준다.

 

Code

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)                # 색상 배열의 길이를 구합니다.
        colors += colors[:k - 1]       # 색상 배열을 원형 배열처럼 만들어줍니다. 첫 번째 원소에서 k-1 개의 원소를 추가합니다.
        answer = 0                         # 교차 그룹의 개수를 저장할 변수 초기화
        cnt = 1                         # 현재 그룹의 길이를 추적하는 변수 초기화
        for i in range(1, len(colors)):    # 색상 배열의 두 번째 원소부터 끝까지 순회
            if colors[i] != colors[i - 1]: # 현재 원소와 이전 원소가 다르면
                cnt += 1                   # 그룹 길이를 증가시킴
            else:                           # 현재 원소와 이전 원소가 같으면
                cnt = 1                    # 새로운 그룹 시작, 길이를 1로 초기화
            
            if cnt >= k:                    # 그룹 길이가 k 이상이면
                answer += 1                    # 교차 그룹의 개수를 1 증가시킴

        return answer

 

Complexity

Time Complexity

배열을 (n+k-1)만큼 순회하므로  O(N)

 

Space Complexity
새로만든 배열의 길이가 n+k-1 이므로 O(N+K)