3208. Alternating Groups II

Problem : https://leetcode.com/problems/alternating-groups-ii

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:14:52

 

---

 

문제 설명

 

 

빨강과 블루 타일로 구성된 원이 있다. 정수 배열 colors와 정수 k가 주어진다. 타일 i의 색상은 colors[i]로 표현된다.

 

* colors[i] == 0은 타일 i가 빨강임을 의미한다.

* colors[i] == 1은 타일 i가 파랑임을 의미한다.

 

교대하는 그룹은 원 안의 k개의 연속되는 모든 타일이 교대하는 색상으로 이루어졌음을 의미한다 (그룹의 첫 번째와 마지막 번째를 제외한 모든 타일이 왼쪽과 오른쪽과는 다른 색상의 타일을 가지고 있음을 의미한다)

 

교대하는 그룹의 개수를 반환하라.

 

colors가 원을 나타내므로, 첫 번째와 마지막 타일은 서로 옆에 있다고 간주된다.

---

 

풀이

 

어제 포스팅한 문제와 근본적으로는 동일하다.

 

2025.03.08 - [PS/LeetCode] - 2379. Minimum Recolors to Get K Consecutive Black Blocks

2379. Minimum Recolors to Get K Consecutive Black Blocks

앞뒤로 패턴을 세어주면 가장 간단하게 풀 수 있다. 결국 원형이므로, 회전하는 개념으로 N을 넘어가는 케이스는 % K로 체크하면 된다. 

 

풀이 코드 1

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        N = len(colors)
        ans = 0
        total = 0
        acnt = 0
        for i in range(N+k-2):
            total += 1
            acnt += colors[i % N] != colors[(i+1) % N]
            if total > k-1:
                total -= 1
                acnt -= colors[(i-k+1) % N] != colors[(i-k+2) % N]
            if total == k-1 == acnt :
                ans += 1
        return ans

 

여기서 조금 더 나아가서, 패턴을 잘 관찰해보자.

k = 3일때, 길이 5의 연속된 alternating group이 있다고 하자('10101', '01010') 그렇다면 k=3인 alternating group은 이 중 3개가 존재한다. 눈치챘는가?

일반화하면, 길이 N의 연속된 alternating group 안에는 N-k+1개의 우리가 목표하는 alternating group이 있다. 따라서, 아까와 같이 무작정 i-k+2번째와 i-k+1번째 이전의 값을 참조할 필요 없이, alternating group을 셀 수 있는 데까지 센 후 위의 공식을 활용해 빠르게 구할 수 있다.

 

풀이 코드 2

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

        for i in range(N+k-2):
            if colors[i % N] == colors[(i+1) % N] :
                ans += max(count-k+2, 0)
                count = 0
            else :
                count += 1
        ans += max(count-k+2, 0)
        return ans