이번 튜토리얼에서는 이진 배열에서 0을 뒤집었을 때 연속된 1의 개수가 최대가 되도록 뒤집어야 할 0의 인덱스를 찾는 방법을 알아보겠습니다.
이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 최대로 뒤집을 수 있는 0의 개수를 초과하지 않는 범위 내에서 가장 긴 연속 구간(윈도우)을 찾는 것입니다.
문제 해결 단계
- 배열과 뒤집을 수 있는 최대 0의 개수(maxZeroes)를 초기화합니다.
- 윈도우의 시작 인덱스(start), 끝 인덱스(end)와 함께 필요한 변수들을 선언합니다.
- 연속된 1의 최대 길이와 해당 윈도우의 시작 인덱스를 저장할 변수를 준비합니다.
- 끝 인덱스가 배열의 길이를 넘지 않을 때까지 배열을 순회합니다.
- 현재 0의 개수가 허용치 이하라면 끝 인덱스를 증가시키고, 현재 값이 0이라면 0의 개수를 증가시킵니다.
- 0의 개수가 허용치를 초과하면 시작 인덱스를 증가시키고, 시작 지점의 값이 0이라면 0의 개수를 감소시켜 윈도우를 축소합니다.
- 현재 윈도우의 길이가 이전에 기록한 최대 길이보다 크면 최대 윈도우 정보를 갱신합니다.
- 순회가 끝나면 기록해둔 윈도우 시작 인덱스를 기준으로 배열을 다시 확인하여, 뒤집어야 할 0의 인덱스를 출력합니다.
C++ 코드 예제
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
int start = 0, end = 0;
int zeroesCount = 0;
int bestWindowCount = 0, bestWindowStartIndex = 0;
while (end < n) {
// 0의 개수가 허용 범위 이내일 때 윈도우 확장
if (zeroesCount <= maxZeroes) {
if (arr[end] == 0) {
zeroesCount++;
}
end++;
}
// 0의 개수가 초과되면 윈도우 축소
if (zeroesCount > maxZeroes) {
if (arr[start] == 0) {
zeroesCount--;
}
start++;
}
// 더 긴 유효한 윈도우를 발견하면 갱신
if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
bestWindowCount = end - start;
bestWindowStartIndex = start;
}
}
cout << "The indexes are ";
for (int i = 0; i < bestWindowCount; ++i) {
if (arr[bestWindowStartIndex + i] == 0)
cout << bestWindowStartIndex + i << " ";
}
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
int maxZeroes = 2;
zeroesIndexes(arr, maxZeroes, 10);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
The indexes are 5 7
배열 {1, 0, 0, 1, 1, 0, 1, 0, 1, 1}에서 인덱스 5와 7의 0을 뒤집으면 1, 1, 1, 1, 1, 1, 1처럼 길이 7의 연속된 1 구간이 만들어지며, 이것이 두 개의 0을 뒤집을 때 얻을 수 있는 최대 길이입니다.
마무리
슬라이딩 윈도우 기법을 활용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.