정수로 이루어진 배열 arr[]가 주어졌을 때, 각 부분 배열 안에서 인접한 두 요소의 차이가 정확히 1이 되는 모든 부분 배열(subarray)의 개수를 구하는 것이 목표입니다. 예를 들어 배열이 [1, 2, 3]이라면 조건을 만족하는 부분 배열은 [1,2], [2,3], [1,2,3] 세 가지뿐입니다.
예제로 이해하기
입력 − arr[] = { 4, 3, 2, 1 }
출력 − 인접 요소의 차이가 1인 부분 배열의 개수: 6
설명 − 만들 수 있는 부분 배열은 다음과 같습니다.
[4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1] → 총 6개
입력 − arr[] = { 1, 5, 6, 7, 9, 11 }
출력 − 인접 요소의 차이가 1인 부분 배열의 개수: 3
설명 − 만들 수 있는 부분 배열은 다음과 같습니다.
[5,6], [6,7], [5,6,7] → 총 3개
풀이 접근 방식
배열을 for 루프로 한 번만 순회하면서 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 조건(인접 요소의 차이가 1)을 만족하는 연속 구간을 찾습니다.
- 길이가 temp인 하나의 연속 구간 안에서 만들 수 있는 길이 2 이상의 부분 배열 개수는 temp × (temp − 1) / 2입니다. 이는 구간 내에서 시작 지점과 끝 지점을 고르는 조합의 수와 같습니다.
- 조건이 깨지는 지점마다 지금까지 구간의 결과를 누적하고, 새로운 구간을 시작합니다.
단계별 알고리즘
- 숫자 배열 arr[]를 준비합니다.
- 함수 sub_ele_diff_one(int arr[], int size)는 배열을 받아 조건을 만족하는 부분 배열의 개수를 반환합니다.
- 결과를 저장할 count를 0으로 초기화합니다.
- 변수 first, last를 0으로 두어, 모든 요소가 연속적이면서 서로 차이가 1인 구간의 끝과 시작 인덱스를 추적합니다.
- i = 1부터 size − 1까지 순회하며 arr[i−1] − arr[i] == 1 또는 arr[i] − arr[i−1] == 1인지 확인합니다. 참이면 first를 증가시켜 현재 구간을 확장합니다.
- 조건이 거짓이면 현재 구간의 길이는 temp = first − last + 1이고, 만들 수 있는 부분 배열 수는 total = temp × (temp − 1) / 2입니다.
- total을 count에 더한 뒤, first와 last를 현재 인덱스 i(연속 조건이 깨진 지점)로 갱신해 새로운 구간을 시작합니다.
- 루프가 끝난 후 first != last라면 마지막 구간 역시 조건을 만족하므로 같은 방식으로 total을 count에 더합니다.
- 모든 과정이 끝나면 count를 결과로 반환합니다.
이 방식은 각 요소를 한 번씩만 확인하므로 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int sub_ele_diff_one(int arr[], int size){
int count = 0, first = 0, last = 0;
for (int i = 1; i < size; i++){
if (arr[i] - arr[i - 1] == 1 || arr[i-1] - arr[i] == 1){
first++;
}
else{
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
first = i;
last = i;
}
}
if (first != last){
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
}
return count;
}
int main(){
int arr[] = { 1, 2, 4, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"인접 요소의 차이가 1인 부분 배열의 개수: "<<sub_ele_diff_one(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
인접 요소의 차이가 1인 부분 배열의 개수: 2
배열 { 1, 2, 4, 3 }에서 조건을 만족하는 부분 배열은 [1,2]와 [4,3] 두 개뿐이므로 결과는 2가 됩니다.