C 언어로 최소 비교 횟수만으로 배열의 최댓값과 최솟값 찾기

정수로 이루어진 배열이 주어졌을 때, 최소한의 비교 횟수만으로 배열의 최댓값과 최솟값을 찾는 것이 이번 글의 목표입니다.

문제 이해하기

입력 1

Arr[] = { 1, 2, 4, 5, -3, 91 }

출력 1

최댓값 : 91
최솟값 : -3

설명 − 비교 횟수를 줄이기 위해 먼저 최댓값(max)과 최솟값(min) 변수를 첫 번째 요소인 Arr[0]으로 초기화합니다. 그다음 두 번째 요소부터 시작해 각 값을 min과 max와 차례로 비교하면서 조건에 맞게 갱신해 나갑니다.

입력 2

Arr[] = { 10, 20, 21, 31, 18, 11 }

출력 2

최댓값 : 31
최솟값 : 10

알고리즘 접근 방식

• 정수들이 담긴 배열 Arr[]를 입력으로 받습니다.

• getresult(int arr[], int n) 함수가 최소한의 비교 횟수로 배열 내의 최댓값과 최솟값을 찾습니다.

• 배열에 요소가 하나뿐이라면 max와 min 변수를 모두 arr[0]으로 초기화하고 바로 반환합니다.

• 요소가 둘 이상인 경우에는 처음 두 요소를 한 번 비교하여 더 큰 값을 max로, 더 작은 값을 min으로 초기화합니다.

• for 루프를 통해 세 번째 요소(i = 2)부터 마지막 요소까지 순차적으로 탐색합니다.

• 각 값(arr[i])을 min 및 max와 비교합니다. min보다 작으면 min을 arr[i]로 갱신하고, max보다 크면 max를 arr[i]로 갱신합니다. 여기서 else if를 사용하면 한 번의 반복당 최대 2번의 비교만 발생하여 전체 비교 횟수를 줄일 수 있습니다.

• 마지막으로 max와 min 변수에 저장된 결과를 출력합니다.

예제 코드

#include <stdio.h>
#include <math.h>
int getresult(int arr[], int n){
    int min=0,max=0;
    /* 요소가 하나뿐이라면 그 값을 min과 max로 모두 지정 */
    if (n == 1)
        { min=max=arr[0]; }
    /* 요소가 둘 이상이라면 처음 두 값을 비교하여 초기화 */
    if (arr[0] > arr[1]){
        max = arr[0];
        min = arr[1];
    }
    else{
        max = arr[1];
        min = arr[0];
    }
    for (int i = 2; i<n; i++){
        if (arr[i] > max)
            max = arr[i];
        else if (arr[i] < min)
            min = arr[i];
    }
    printf(" Minimum element: %d", min);
    printf(" Maximum element: %d", max);
}
/* 위 함수를 테스트하기 위한 드라이버 프로그램 */
int main(){
    int arr[] = {200, 191, 112, -11, 330, 60};
    int n = 6;
    getresult (arr, n);
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Minimum element: -11
Maximum element: 330