정수로 이루어진 배열 arr[]와 양의 정수 k가 주어졌을 때, 요소 사이의 절대 차이가 k를 초과하지 않는 조건을 만족하면서 함께 묶을 수 있는 최대 요소 수를 계산하는 것이 이번 문제의 목표입니다.
배열(array)은 같은 자료형의 요소들을 고정된 크기로 순차적으로 저장하는 가장 기본적인 자료구조 중 하나입니다. 여러 개의 데이터를 하나의 이름 아래 관리할 수 있어, 동일한 타입의 변수들을 모아둔 컬렉션으로 생각하면 훨씬 직관적으로 이해할 수 있습니다.
예제
입력 − int arr[] = {2, 3, 6, 12, 14}, k = 5
출력 − 개수 : 3설명 − 절대 차이가 k(이 예제에서는 5)를 초과하지 않는 쌍은 (2, 3), (2, 6), (3, 6)이며, 이는 곧 {2, 3, 6}이라는 그룹을 형성합니다. 따라서 최대 요소 수는 3입니다.
입력 − int arr[] = {2, 3, 6, 12, 14}, k = 10
출력 − 개수 : 4설명 − 절대 차이가 k(이 예제에서는 10)를 초과하지 않는 쌍은 (2, 3), (2, 6), (3, 6), (2, 12), (3, 12), (6, 12)이며, 이는 {2, 3, 6, 12}에 해당합니다. 따라서 최대 요소 수는 4입니다.
입력 − int arr[] = {2, 3, 6, 12, 14}, k = 0
출력 − 개수 : 0설명 − 서로 다른 두 요소의 차이가 0이 되는 쌍은 존재하지 않으므로 개수는 0입니다.
문제 해결 접근 방식
이 문제는 정렬과 투 포인터(슬라이딩 윈도우) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별 접근 방식은 다음과 같습니다.
- 배열 arr[]와 양의 정수 k를 준비합니다.
- 배열의 크기를 계산합니다. (sizeof 연산자 또는 length() 함수 활용)
- 최대 개수를 저장할 임시 변수 result를 선언합니다.
- 투 포인터로 사용할 변수 i와 j를 0으로 초기화합니다.
- sort() 함수를 호출해 배열을 오름차순으로 정렬합니다.
- i를 0부터 배열 크기 미만까지 반복하는 for 루프를 실행합니다.
- 루프 안에서 j < size이면서 arr[j] <= arr[i] + k를 만족하는 동안 j를 증가시키는 while 루프를 실행합니다.
- while 루프가 끝난 후 result < (j - i)라면 result를 j - i로 갱신하고, 시작 인덱스(beg)와 끝 인덱스(end)를 기록합니다.
- 모든 반복이 끝나면 result를 반환합니다.
- main 함수에서 결과를 출력합니다.
배열을 오름차순으로 정렬하면 arr[i]부터 시작하는 구간의 모든 요소가 arr[i] + k 이하임을 보장할 수 있습니다. 따라서 두 포인터를 이동시켜 가장 넓은 구간의 길이를 찾으면 그것이 곧 정답이 됩니다. 전체 시간 복잡도는 정렬 O(n log n)과 탐색 O(n)을 합쳐 O(n log n)입니다.
예제 코드
#include <iostream>
#include <algorithm>
using namespace std;
int countmax(int arr[], int size, int K){
int result = 0;
int i = 0, j = 0;
int beg = 0;
int end = 0;
// 배열을 오름차순으로 정렬
sort(arr, arr + size);
// 조건을 만족하는 최대 요소 수 찾기
for (i = 0; i < size; i++) {
// 범위 안에 속하는 모든 요소 개수 세기
while (j < size && arr[j] <= arr[i] + K)
j++;
if (result < (j - i)) {
result = (j - i);
beg = i;
end = j;
}
}
// 최대 개수 반환
return result;
}
// main 함수
int main(){
int arr[] = { 2, 3, 6, 12, 14 };
int size = sizeof(arr) / sizeof(arr[0]);
int K = 5;
cout << "count is " << countmax(arr, size, K) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 확인할 수 있습니다.
count is 3