이 문제에서는 하나의 배열과 정수 k가 주어집니다. 우리의 과제는 최댓값이 k인 서로 겹치지 않는(non-overlapping) 부분 배열들을 찾아, 그 길이들의 합이 최대가 되도록 하는 프로그램을 C++로 작성하는 것입니다.
문제 설명
배열과 정수 k가 주어졌을 때, 이 배열에서 만들 수 있는 모든 겹치지 않는 부분 배열 중 최댓값이 정확히 k인 부분 배열들을 찾아야 합니다. 그런 다음, 찾은 부분 배열들의 길이를 모두 더한 값을 결과로 반환합니다.
예제로 이해하기
입력 — array = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5}, k = 3
출력 — 7
설명 — 최댓값이 3인 겹치지 않는 부분 배열은 다음과 같습니다.
{3} : 길이 = 1
{1, 2, 3, 1} : 길이 = 4
{3, 2} : 길이 = 2
길이의 합 = 1 + 4 + 2 = 7해결 접근 방법
이 문제는 배열을 한 번만 순회하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
배열을 왼쪽부터 오른쪽으로 탐색하면서, k보다 작거나 같은 값들로 이루어진 연속 구간을 추적합니다. 각 구간에 대해 다음 두 가지 정보를 유지합니다.
- 구간의 길이(subarrayLength): 현재 연속 구간에 포함된 원소의 개수
- 플래그(flag): 현재 구간 안에 값이 정확히 k인 원소가 존재하는지 여부
k보다 큰 값을 만나면 현재 구간이 끝난 것이므로, 플래그가 설정되어 있었다면(즉, 구간에 k가 포함되어 있었다면) 그 구간의 길이를 합계에 더합니다. k보다 큰 값들은 구간을 나누는 경계 역할을 하며, 건너뛰고 다음 구간 탐색을 계속합니다.
이렇게 하면 최댓값이 k인 모든 겹치지 않는 부분 배열의 길이 합을 정확하게 구할 수 있습니다.
구현 예제
위 접근 방식의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
int subArrayLengthSum(int arr[], int n, int k){
int lengthSum = 0;
int subarrayLength = 0;
int flag = 0;
for (int i = 0; i < n;) {
subarrayLength = 0;
flag = 0;
// k보다 작거나 같은 값으로 이루어진 구간 탐색
while (arr[i] <= k && i < n) {
subarrayLength++;
if (arr[i] == k)
flag = 1;
i++;
}
// 구간에 k가 포함되어 있으면 길이를 합산
if (flag == 1)
lengthSum += subarrayLength;
// k보다 큰 값은 건너뛰기
while (arr[i] > k && i < n)
i++;
}
return lengthSum;
}
int main(){
int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
int ans = subArrayLengthSum(arr, size, k);
cout<<"최댓값이 "<<k<<"인 겹치지 않는 부분 배열의 길이 합의 최댓값은 "<<ans;
return 0;
}
출력 결과
최댓값이 3인 겹치지 않는 부분 배열의 길이 합의 최댓값은 7
복잡도 분석
- 시간 복잡도: O(n) — 배열의 각 원소를 최대 한 번씩만 방문합니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 몇 개의 변수만 사용합니다.
이 알고리즘은 단일 패스(single pass)로 동작하기 때문에 매우 효율적이며, 대용량 배열에도 적합합니다.