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.
빨간색과 파란색 타일을 가진 원이 있다.
integer한 값을 가진 배열과 k가 주어진다.
타일의 i번째 색상은 colors[i]이다. (무슨소린지 모르겠음)
colors[i] == 0 은 빨간색이다.
colors[i] == 1 은 파란색이다.
번갈아가는 그룹은 번갈아가는 색상과 함께 원 안의 모든 k개의 연속적인 타일이다.
번갈아가는 그룹의 개수를 return하라.
첫번째와 마지막 타일은 서로 옆에 붙은거로 간주해라.
해석을 해보긴 했는데,, 이것만 봐서는 이해가 잘 안된다.
예시를 보자
연속하는 타일 6개를 선택하는데 이 타일들의 색깔이 반복되어야 한다는 문제같다.
Solution
접근방식
-
원형연결리스트를 만든다. (귀찮음)
1-1. 원형연결리스트를 가장 간단하게 만드는 방법은 배열 * i번 하는것이다.
[0,1,0,0,1,0,1] 여기에서 [0,1,0,0,1,0,1 | 0,1,0,0,1,0,1 ... ] 똑같이 반복해주면 결국 원형으로 도는거나 다름없다.
1-2. 배열로 변경했을때 배열의 크기를 생각해보자.
기존 colors 배열 에서 k개만큼만 더 확인하면 되니까 배열의 크기는
[colors.length - 1 + k]가 될것이다. -
투포인터를 사용해서 색상비교를 할것이다.
left, right변수를 사용할것이고
right는 right+1 원소와 비교해서 색상이 다르다면 ++ 해주는식으로.left는 언제 이동하느냐?
right와 right + 1 이 서로 다르다면 어차피 right까지 left가 이동해도된다.그리고 right와 left의 길이가 k와 같다면 result의 개수가 증가하고 left++ 하면 된다.
Code
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int result = 0;
int[] copy = new int[colors.length - 1 + k];
for(int i= 0 ; i< colors.length; i++){
copy[i] = colors[i];
}
for(int i = colors.length; i < copy.length; i++){
copy[i] = colors[i - colors.length];
}
int l = 0;
int r = 0;
while(r + 1< copy.length ){
if(copy[r] != copy[r + 1]){
r++;
}else{
r = r + 1;
l = r;
}
if(r - l + 1== k) {
result++;
l++;
}
}
return result;
}
}
