[LeetCode] 3208. Alternating Groups II (Python)

 

난이도: Medium

Problem Description

---

There is a circle of red and blue tiles. You are given an array of integers colors and an integer k. The color of tile i is represented by colors[i]:

• colors[i] == 0 means that tile i is red.
• colors[i] == 1 means that tile i is blue.

An alternating group is every k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).

 

Return the number of alternating groups.

 

Note that since colors represents a circle, the first and the last tiles are considered to be next to each other.

 

Problem Example

---

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:

 

Constraints

---

• 3 <= colors.length <= 105
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

 

✏️ Solution

---

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        answer = 0

        cnt = 1
        for i in range(-k+1, n-1):
            if colors[i] == colors[i-1]:
                cnt = 1
            else:
                cnt += 1
            
            if cnt == k:
                answer += 1
                cnt -= 1

        return answer

 

Sliding Window 기법으로 해결할 수 있었다.

 

입력으로 주어지는 리스트는 일반적인 리스트가 아니라 원형 리스트로 생각해야하기 때문에 for문의 range를 -k+1부터 n-1까지 설정햇다.

 

현재 색깔 color[i]와 이전 색깔 color[i-1]이 같지 않다면 cnt를 +1씩 해주었다.

만약 현재 색깔과 이전 색깔이 같다면 cnt를 1로 만들어주었다.

 

이 과정에서 cnt의 수가 k와 같아지면 answer를 +1 해주고 cnt를 -1해주었다.

 

마지막에는 이러한 answer를 반환하여 정답을 맞출 수 있었다.

⚙️ Runtime & Memory

---

 

 

---

문제: 3208. Alternating Groups II

 

깃허브: github

algorithmPractice/LeetCode/3483-alternating-groups-ii at main · laewonJeong/algorithmPractice