문제 개요
임의의 크기를 가진 정수 배열이 주어졌을 때, 인접한 두 요소의 차이가 0 또는 1이 되는 가장 긴 연속 부분 배열(subarray)의 길이를 찾는 것이 이번 문제의 목표입니다.
예제 1
입력: int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }
출력: 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 배열: 2
설명: 배열에서 인접 요소 간의 차이가 0 또는 1을 만족하는 구간은 {2, 1}, {5, 6}, {3, 4}, {7, 6}입니다. 모든 구간의 길이가 2이므로 부분 배열의 최대 길이는 2가 됩니다.
예제 2
입력: int arr[] = { 2, 1, 7, 6, 5 }
출력: 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 배열: 3
설명: 조건을 만족하는 구간은 {2, 1}과 {7, 6, 5}입니다. 이 중 가장 긴 구간은 {7, 6, 5}이므로 최대 길이는 3입니다.
알고리즘 접근 방식
- 양수와 음수를 모두 포함할 수 있는 정수형 배열을 입력받습니다.
- 배열의 크기를 계산한 후, 이후 처리를 위해 배열과 크기를 함수에 전달합니다.
- 임시 변수 i를 0으로 초기화하고, 최댓값을 저장할 변수 maximum 역시 0으로 초기화합니다.
- i가 배열의 크기보다 작은 동안 while 루프를 실행합니다.
- 루프 내부에서 j를 i로 설정하여 현재 탐색 구간의 시작 위치를 기록합니다.
- 인접 요소 간의 차이가 0 또는 1인지 검사하며 구간을 확장하는 내부 루프를 실행합니다.
- 내부 루프 안에서는 조건이 만족되는 동안 i 값을 계속 증가시킵니다.
- temp를 i - j + 1로 설정하여 현재 구간의 길이를 계산합니다.
- maximum이 temp보다 작으면 maximum을 temp로 갱신합니다.
- j와 i가 같다면(구간이 확장되지 않았다면) i를 증가시켜 다음 요소로 이동합니다.
- 최종적으로 maximum을 반환하고 결과를 출력합니다.
이 알고리즘은 각 요소를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 상수 공간(O(1))으로 해결할 수 있는 효율적인 방법입니다.
C++ 코드 예제
#include<bits/stdc++.h>
using namespace std;
// 인접 요소 간의 차이가 0 또는 1인
// 최대 길이 부분 배열을 계산하는 함수
int maximum_diff(int arr[], int size){
int i = 0;
int maximum = 0;
while (i < size){
int j = i;
while (i+1 < size && (abs(arr[i] - arr[i + 1]) == 1 || abs(arr[i] - arr[i + 1]) == 0)){
i++;
}
int temp = i - j + 1;
if (maximum < temp){
maximum = temp;
}
if(j == i){
i++;
}
}
return maximum;
}
int main(){
int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 배열: "<< maximum_diff(arr, size);
}
출력 결과
인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 배열: 2