문)

            크기가 5이고 각 배열의 값은 1~4로 한정된 정수 배열에서 첫번째 중복 수가 발생한 경우의 첫번째 값과 인덱스를 반환한다.

            (가정. 중복수의 발생은 무조건 있다)

            C/C++을 활용하여 작성.



사용 예)

             int a[5] = {1,2,3,4,3};

             int b, result;

             result = rtnValIndex(a, &b);

             printf("index = %d, result = %d ", b, result);


출력 예)

             index = 2, result = 3


O(n²) 구현)

int rtnValIndex(int* a, int* b){

int i, j, check = 0;
for(i=0; i<5; i++){

if(check != 0)
   break;
for(j=i+1; j<5; j++){
       if(a[i] == a[j]){
            *b = i;
            check = 1;
            break;
      }
}

}
 return a[*b];

}


--------------------------------------------------------------------------------

여기서 rtnValIndex함수를 시간복잡도 O(n)에 맞게 수정하고싶은데 어떻게하면 될까?