[코테연습] 3208. Alternating Groups II

https://leetcode.com/problems/alternating-groups-ii/description/?envType=daily-question&envId=2025-03-09

 

 

문제 유형:

• 배열(Array)​
• 슬라이딩 윈도우(Sliding Window)​

문제 분석:

• 주어진 배열 colors는 빨간색(0)과 파란색(1) 타일로 구성된 원형 배열입니다.​
• 정수 k가 주어지며, 길이 k의 연속된 타일이 교대로 색상이 배치된 부분 배열의 개수를 찾아야 합니다.​
• 원형 배열이므로 배열의 끝과 시작이 연결되어 있습니다.​

문제 풀이:

• 원형 배열의 특성을 처리하기 위해 colors 배열을 확장하여 첫 k-1개의 요소를 배열 끝에 추가합니다.​
• 슬라이딩 윈도우 기법을 사용하여 확장된 배열을 탐색하며, 인접한 타일의 색상이 다르면 현재 교대 그룹의 길이를 증가시킵니다.​
• 만약 인접한 타일의 색상이 같다면, 현재 교대 그룹의 길이를 1로 초기화합니다.​
• 교대 그룹의 길이가 k 이상이 되면, 이는 유효한 교대 그룹으로 간주하여 결과를 증가시킵니다.​
• 이러한 과정을 통해 원형 배열에서 길이 k의 교대 색상 패턴의 개수를 효율적으로 계산할 수 있습니다.

 

 

1. 원형 배열 처리

🔹 배열을 확장하는 이유

원형 배열에서 길이 k의 연속된 부분 배열을 확인해야 합니다.
즉, 배열의 끝을 넘어가 다시 처음으로 돌아오는 경우도 고려해야 합니다.

예를 들어, 

colors = [1, 2, 3], k = 2

 

가능한 부분 배열:

(1,2), (2,3), (3,1), (1,2)

 

위에서 볼 수 있듯이 **(3,1)**과 같은 구간이 나오므로, 배열을 확장하여 이를 쉽게 처리할 수 있습니다.

 

---

🔹 배열 확장 코드

int[] temp = new int[n + k - 1];

System.arraycopy(colors, 0, temp, 0, n);

System.arraycopy(colors, 0, temp, n, k - 1);

✅ 이 코드의 역할

1. temp는 colors 배열을 확장하여 원형 배열처럼 동작하도록 만듭니다.
2. System.arraycopy(colors, 0, temp, 0, n);
   • colors 배열을 temp에 그대로 복사합니다.
3. System.arraycopy(colors, 0, temp, n, k - 1);
   • colors의 첫 번째 k-1개 요소를 temp의 끝부분에 추가합니다.

🔹 예제 (colors = [1,2,3], k=2)

temp = [1, 2, 3, 1] // 원형 배열처럼 동작하게 변형됨

 

이제, temp에서 길이 k의 연속 부분 배열을 쉽게 찾을 수 있습니다.

 

 

2. 슬라이딩 윈도우를 활용한 교대 그룹 탐색

배열이 확장되었으므로, temp에서 길이 k의 부분 배열을 찾으면 됩니다.
슬라이딩 윈도우를 이용해 탐색합니다.

int count = 0; // 교대 패턴 개수

int left = 0; // 현재 윈도우의 시작점

• count는 교대 패턴 개수를 세는 변수
• left는 현재 슬라이딩 윈도우의 시작점

🔹 메인 탐색 루프

for (int right = 0; right < temp.length; right++) {

• right는 현재 탐색 위치로, temp를 처음부터 끝까지 탐색합니다.

 

3. 연속된 값이 같으면 윈도우 재설정

if (right > 0 && temp[right] == temp[right - 1]) { left = right; // 같은 값이 나오면 새로운 시작점으로 이동 }

✅ 이 코드의 역할

1. temp[right] == temp[right - 1]
   • 현재 값과 이전 값이 같다면, 교대 패턴이 아니므로 새로운 시작점 left를 갱신합니다.
   • 즉, left를 right로 설정하여 중복이 발생한 위치부터 다시 탐색합니다.

 

4. 길이 k 이상이면 카운트 증가

if (right - left + 1 >= k) { count++; }

✅ 이 코드의 역할

• right - left + 1 → 현재 슬라이딩 윈도우 크기
• 만약 현재 윈도우의 길이가 k 이상이면, 교대 패턴을 만족하는 부분 배열이므로 count 증가

전체 동작 예시

🔹 입력 예시

colors = [1, 2, 3] k = 2

🔹 배열 확장 후

temp = [1, 2, 3, 1]

🔹 탐색 과정

righttemp[right]left현재 윈도우 (right - left + 1)추가되는 패턴

0	1	0	1	X
1	2	0	2	✅ (1,2)
2	3	0	3	✅ (1,2,3)
3	1	0	4	✅ (1,2,3,1)

최종 count = 3

 

> java

 

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;

        // 원형 배열 처리를 위해 배열을 확장
        // colors 배열을 두 번 이어붙여 k-1 길이만큼 추가 확장
        int[] temp = new int[n + k - 1];
        System.arraycopy(colors, 0, temp, 0, n);
        System.arraycopy(colors, 0, temp, n, k - 1); 

        int count = 0;  // 교대 그룹 개수
        int left = 0;   // 유효한 연속 부분 시작점
        
        // 슬라이딩 윈도우 방식으로 탐색
        for (int right = 0; right < temp.length; right++) {
            // 인접한 두 색이 동일하면 새로운 시작점으로 이동
            if (right > 0 && temp[right] == temp[right - 1]) {
                left = right;  // 새로운 구간 시작점 갱신
            }

            // 현재 윈도우 크기가 k 이상이면 유효한 교대 그룹이므로 카운트 증가
            if (right - left + 1 >= k) {
                count++;  
            }
        }
        
        return count;
    }
}