크기가 N인 정수 배열이 하나 주어지며, 배열에는 정수들이 무작위 순서로 들어 있습니다. 이 문제의 목표는 배열에서 특정 요소가 처음 등장하는 인덱스(첫 번째 인덱스)와 마지막으로 등장하는 인덱스 사이의 최대 차이를 구하는 것입니다. 즉, 배열에 두 번 이상 나타나는 숫자를 찾아 그 인덱스 간 차이가 가장 큰 값을 계산해야 하며, 해당하는 쌍이 여러 개라면 그중 최대 차이를 결과로 저장합니다.
입력 예시 1
Arr[] = { 2,1,3,1,3,2,5,5 }출력 − 배열에서 요소의 첫 번째 인덱스와 마지막 인덱스 간 최대 차이 − 5
설명 − 각 요소 쌍과 인덱스 차이는 다음과 같습니다 −
(2,2) Arr[0]과 Arr[5] → 5-0=5, 현재까지 최대 차이는 5 (1,1) Arr[1]과 Arr[3] → 3-1=2, 현재까지 최대 차이는 5 (3,3) Arr[2]과 Arr[4] → 4-2=2, 현재까지 최대 차이는 5 (5,5) Arr[6]과 Arr[7] → 7-6=1, 현재까지 최대 차이는 5
입력 예시 2
Arr[] = { 2,2,3,4,8,3,4,4,8,7 }출력 − 배열에서 요소의 첫 번째 인덱스와 마지막 인덱스 간 최대 차이 − 4
설명 − 각 요소 쌍과 인덱스 차이는 다음과 같습니다 −
(2,2) Arr[0]과 Arr[1] → 1-0=1, 현재까지 최대 차이는 1 (3,3) Arr[2]과 Arr[5] → 5-2=3, 현재까지 최대 차이는 3 (4,4,4) Arr[3], Arr[6], Arr[7] → 7-6=1, 6-3=3, 7-3=4, 현재까지 최대 차이는 4 (8,8) Arr[4]과 Arr[8] → 8-4=4, 현재까지 최대 차이는 4
프로그램에서 사용한 접근 방식
- 반복되는 숫자가 무작위 순서로 포함된 정수 배열을 선언합니다. (Arr[])
- 배열의 크기를 저장할 변수를 생성합니다. (N)
- maxDifference(int Arr[], int n) 함수는 배열에서 요소의 첫 번째 인덱스와 마지막 인덱스 간의 최대 차이(maxD)를 계산하는 데 사용됩니다.
- maxDifference() 함수 내부에는 지금까지 발견한 최대 인덱스 차이를 저장하는 변수 maxD를 선언합니다.
- 첫 번째 요소(인덱스 i=0)부터 시작해 for 루프로 배열을 순회합니다.
- 중첩된 for 루프에서는 나머지 부분(j=i+1부터)을 마지막 인덱스까지 순회합니다.
- Arr[i]와 같은 값을 가진 요소를 찾으면 두 인덱스 i, j의 차이를 계산하고, 이 값이 기존 maxD보다 크면 maxD를 갱신합니다.
- 바깥쪽과 안쪽 for 루프가 모두 종료될 때까지 이 과정을 반복합니다.
- maxD에 저장된 결과를 반환합니다.
예제 코드
#include <stdio.h>
int maxDifference(int arr[], int n){
int maxD = 0;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(arr[i] == arr[j] && (j-i) > maxD)
maxD = j-i;
}
}
return maxD;
}
int main(){
int Arr[] = {1, 4, 1, 3, 3, 5, 4, 5, 2};
int N = sizeof(Arr) / sizeof(Arr[0]);
printf("Maximum difference between first and last indexes of an element in array : %d", maxDifference(Arr, N));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Maximum difference between first and last indexes of an element in array : 5
이 알고리즘은 두 개의 중첩 루프를 사용하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 매우 큰 경우에는 해시 테이블을 활용해 각 요소의 첫 등장 인덱스만 저장한 뒤 배열을 한 번만 순회함으로써 O(n) 시간 복잡도로 문제를 해결할 수도 있습니다.