정수로 이루어진 배열이 주어지며, 이 배열에는 동일한 요소가 여러 번 등장할 수 있습니다. 이 문제의 목표는 배열에서 같은 요소 두 개 사이의 최대 거리를 찾는 것입니다.
해결 방법은 다음과 같습니다. 배열의 왼쪽부터 각 요소를 하나씩 선택한 뒤, 그 숫자가 마지막으로 나타나는 위치를 찾아 인덱스 간의 차이를 계산합니다. 이 차이가 지금까지 발견한 값 중 가장 크다면 결과로 저장하고, 모든 탐색이 끝난 후 최종 값을 반환하면 됩니다.
입력 및 출력 예시
예시 1
Arr[] = { 1,2,4,1,3,4,2,5,6,5 }출력: 배열에서 동일한 요소 두 개 사이의 최대 거리 − 4
설명: 반복되는 숫자와 해당 인덱스는 다음과 같습니다.
1. 숫자 1 : 첫 번째 인덱스 0, 마지막 인덱스 3 → 거리 = 3-0-1 = 2 2. 숫자 2 : 첫 번째 인덱스 1, 마지막 인덱스 6 → 거리 = 6-1-1 = 4 3. 숫자 5 : 첫 번째 인덱스 7, 마지막 인덱스 9 → 거리 = 9-7-1 = 1 동일한 요소 두 개 사이의 최대 거리 : 4
예시 2
Arr[] = { 10,20,1,10,10,21,12,0 }출력: 배열에서 동일한 요소 두 개 사이의 최대 거리 − 3
설명:
1. 숫자 10 : 첫 번째 인덱스 0, 마지막 인덱스 4 → 거리 = 4-0-1 = 3 동일한 요소 두 개 사이의 최대 거리 : 3
참고: 입력 배열에 반복되는 숫자가 전혀 없다면 -1을 반환해야 합니다.
프로그램의 접근 방식
- 반복되는 숫자를 포함하는 정수 배열 Arr[]를 입력으로 받습니다.
- maxDistance(int arr[], int n) 함수는 동일한 요소 두 개 사이의 최대 거리를 계산하는 역할을 합니다.
- 결과를 저장할 변수 maxD를 -1로 초기화합니다.
- 바깥쪽 for 루프로 배열을 처음부터 끝까지 순회합니다.
- 안쪽(중첩) for 루프로 나머지 요소들을 탐색하면서 중복되는 값이 있는지 확인합니다. (조건: arr[i] == arr[j])
- 중복이 발견되면 인덱스의 차이를 계산합니다. (temp = j - i - 1)
- 계산된 값이 지금까지의 최댓값보다 크면 maxD에 저장합니다.
- 배열 전체를 순회한 후 maxD를 반환합니다.
예제 코드
#include <stdio.h>
#include <math.h>
int maxDistance(int arr[],int n){
int size = n;
int maxD = -1;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == arr[j]){
int temp=abs(j-i-1);
maxD = maxD>temp?maxD:temp;
}
return maxD;
}
// 드라이버 코드
int main(){
int Arr[] = {1,2,4,1,3,4,2,5,6,5};
printf("배열에서 동일한 요소 두 개 사이의 최대 거리:%d", maxDistance(Arr,10) );
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
배열에서 동일한 요소 두 개 사이의 최대 거리 − 4