문제 소개
첫 N개의 자연수를 순열 형태로 나열한 배열이 주어졌을 때, 아래 조건을 만족하는 요소들의 인덱스 쌍을 찾는 것이 목표입니다.
배열을 Arr[]이라 하고 i, j를 인덱스라고 할 때, 다음 식을 만족하는 요소 쌍의 개수를 구합니다.
Arr[i] + Arr[j] = max(Arr[x]) (단, i ≤ x ≤ j)
즉, Arr[i]와 Arr[j]의 합이 두 인덱스 사이 구간에서 가장 큰 값과 같아야 합니다.
입력 예시 1
Arr[]= { 2,4,1,3,6,5 }출력
조건을 만족하는 인덱스 쌍의 개수: 1
설명 − 각 쌍의 합은 다음과 같습니다.
- 2+4=6 → 6은 최댓값이지만 2와 4 사이에 위치하지 않습니다.
- 2+1=3 → 3은 2와 1 사이에 없으며, 두 구간 사이의 최댓값은 4입니다.
- 2+3=5 → 5는 2와 3 사이에 없으며, 두 구간 사이의 최댓값은 4입니다.
- 2+6=8 → 8은 2와 6 사이에 없으며, 두 구간 사이의 최댓값은 4입니다.
- 1+5=6 → 6은 1과 5 사이에 위치하고, 두 구간 사이의 최댓값 역시 6입니다.
모든 경우를 살펴본 결과 조건을 만족하는 쌍은 단 1개뿐입니다.
입력 예시 2
Arr[]= { 1,2,5,4,3 }출력
조건을 만족하는 인덱스 쌍의 개수: 2
설명 − 각 쌍의 합은 다음과 같습니다.
- 1+5=6 → 6은 최댓값이지만 1과 5 사이에 위치하지 않습니다.
- 1+4=5 → 5는 1과 4 사이에 위치하고, 두 구간 사이의 최댓값 역시 5입니다.
- 2+3=5 → 5는 2와 3 사이에 위치하고, 두 구간 사이의 최댓값 역시 5입니다.
- 1+3=4 → 4는 1과 3 사이에 위치하지만, 두 구간 사이의 최댓값은 5입니다.
모든 경우 중 조건을 만족하는 쌍은 2개입니다.
접근 방법
위 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 정수 배열 Arr[]에 숫자들을 저장하고, size에는 배열의 길이를 담습니다.
- countPairs(int A[], int n) 함수는 배열과 그 크기 n을 입력으로 받아 위 조건을 만족하는 쌍의 개수를 반환합니다.
- 변수 count는 조건을 만족하는 쌍의 개수를 저장하며 초기값은 0입니다.
- max1은 첫 번째 요소로, maxindex는 0으로 초기화하여 지금까지 발견한 최댓값과 그 인덱스를 저장합니다.
- for 반복문으로 배열을 순회합니다.
- 중첩된 for 반복문 안에서 A[j] ≥ max1이면 max1과 그 인덱스를 j로 갱신합니다.
- 각 쌍 A[i], A[j]에 대해 합이 max1과 같고 maxindex가 i와 j 사이에 있다면 조건이 충족되므로 count를 증가시킵니다.
- 두 반복문이 모두 끝나면 count에 저장된 결과를 반환합니다.
예제 코드
// 접근 방법의 C++ 구현
#include<bits/stdc++.h>
using namespace std;
// 조건을 만족하는 인덱스 쌍의 개수를 반환하는 함수
int countPairs(int A[], int n){
// 필요한 개수를 저장할 변수
int count = 0;
int i,j,k;
int max1=A[0];
int maxindex=0;
for ( i = 0; i<n-1; i++){
for(j=i+1;j<n;j++){
if(A[j]>=max1){
max1=A[j];
maxindex=j;
}
if(A[i]+A[j]==max1 && maxindex>=i && maxindex<=j)
count++;
}
}
// 구간 쌍의 개수 반환
return count;
}
int main(){
int Arr[] = {3, 4, 6, 1, 5, 2};
int size =6;
cout <<endl<<"조건을 만족하는 인덱스 쌍의 개수:"
<<countPairs(Arr,size);
return 0;
}
실행 결과
조건을 만족하는 인덱스 쌍의 개수: 1
복잡도 분석
두 개의 중첩된 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 또한 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.