이 글에서는 C++을 사용하여 최댓값과 최솟값이 동일한 부분 배열(subarray)의 개수를 찾는 문제를 해결해 보겠습니다. 먼저 문제의 예시를 살펴보겠습니다.
입력 : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
출력 : 12
설명 : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4}, {4,4,4}가 최댓값과 최솟값이 같은 부분 배열입니다.
입력 : array = { 3,3,1,5,1,2,2 }
출력 : 9
설명 : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3}, {2,2}가 최댓값과 최솟값이 같은 부분 배열입니다.문제 해결 접근 방법
예시를 분석해 보면, 최댓값과 최솟값이 같은 부분 배열의 최소 개수는 배열의 크기와 같다는 것을 알 수 있습니다. 이는 길이가 1인 각 원소 자체가 항상 조건을 만족하는 부분 배열이기 때문입니다. 그리고 연속된 동일한 숫자가 존재하면 부분 배열의 개수는 더 늘어납니다.
따라서 다음과 같은 방식으로 문제를 풀 수 있습니다. 모든 원소를 순회하면서 각 원소 뒤에 연속된 같은 숫자가 몇 개 있는지 확인하고, 같은 숫자가 발견될 때마다 카운트를 증가시킵니다. 다른 숫자를 만나면 내부 반복문을 종료합니다.
내부 반복문이 끝나거나 중단될 때마다 결과 변수에 카운트 값을 더하고, 마지막에 결과 변수에 저장된 값을 출력합니다.
구현 예제 (O(n²) 방식)
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[ ] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = n, count = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(a[i] == a[j])
count++;
else
break;
}
result += count;
count = 0;
}
cout << "최댓값과 최솟값이 같은 부분 배열의 개수:" << result;
return 0;
}
출력 결과
최댓값과 최솟값이 같은 부분 배열의 개수: 9
시간 복잡도 = O(n²)
코드 설명
이 코드에서는 변수 n에 배열의 크기를 저장하고, result를 n으로 초기화합니다. 그 이유는 길이가 1인 부분 배열만 세더라도 최소 n개가 만들어지기 때문입니다. count 변수는 연속된 같은 숫자의 개수를 세는 데 사용됩니다.
외부 반복문은 배열의 모든 원소를 처리하고, 내부 반복문은 현재 인덱스 이후에 연속된 같은 숫자가 몇 개인지 확인합니다. 내부 반복문이 끝날 때마다 count 값을 result에 더하며, 최종적으로 result에 저장된 값을 출력합니다.
효율적인 접근 방법 (O(n))
위 방법은 시간 복잡도가 O(n²)이므로, 더 효율적으로 개선할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 연속된 같은 숫자가 k개 있을 때, 이들로 만들 수 있는 부분 배열의 개수는 조합 공식 "k × (k + 1) / 2"로 한 번에 계산할 수 있습니다.
배열을 한 번만 순회하면서 연속된 같은 숫자의 개수를 세고, 다른 숫자를 만나면 해당 구간에서 만들 수 있는 부분 배열의 개수를 공식으로 계산하여 결과에 더하는 방식입니다.
구현 예제 (O(n) 방식)
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
int count = 1, temp = a[0];
for (int i = 1; i < n; i++) {
if (temp == a[i]){
count++;
}
else{
temp = a[i];
result = result + (count * (count + 1) / 2);
count = 1;
}
}
result = result + (count * (count + 1) / 2);
cout << "최댓값과 최솟값이 같은 부분 배열의 개수:" << result;
return 0;
}
출력 결과
최댓값과 최솟값이 같은 부분 배열의 개수: 9
시간 복잡도 : O(n)
코드 설명
이 코드에서는 배열의 0번째 원소를 temp 변수에 저장하고, 반복문을 인덱스 1부터 시작합니다. temp 값이 현재 인덱스의 원소와 같으면 count를 1씩 증가시켜 연속된 같은 숫자의 개수를 셉니다.
temp 값과 다른 원소를 만나면, 지금까지 센 count로 만들 수 있는 부분 배열의 개수를 공식(count × (count + 1) / 2)으로 계산하여 result에 더합니다. 그런 다음 temp를 현재 원소로 갱신하고 count를 1로 초기화합니다. 반복문이 끝난 후에는 마지막 구간에 대한 계산을 한 번 더 수행해야 하므로, 공식을 마지막에 한 번 더 적용합니다.
마무리
이 글에서는 최댓값과 최솟값이 같은 부분 배열의 개수를 찾는 문제를 다루었습니다. 단순한 이중 반복문 방식(O(n²))과 조합 공식을 활용한 효율적인 방식(O(n)) 두 가지 접근 방법을 C++ 코드와 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 알고리즘 학습에 도움이 되기를 바랍니다.