C++에서 관계 연산자 없이 배열의 최솟값 찾기

문제 개요

n개의 양의 정수로 이루어진 배열 arr[]가 주어졌을 때, 관계 연산자(relational operator)를 사용하지 않고 배열에서 최솟값을 찾아야 합니다.

관계 연산자란 두 값 사이의 대소 관계를 판별하는 연산자로, ==(같음), >(크다), <(작다) 등이 여기에 해당합니다. 즉, if(a < b)처럼 값을 직접 비교하는 문법 없이 최솟값을 구해야 하는 것이 이 문제의 핵심 조건입니다.

예제

입력

arr[] = {4, 2, 5, 1, 7}

출력

1

설명

배열에서 가장 작은 요소는 1입니다.

해결 접근 방식

가장 기본적인 방법은 반복문으로 배열 전체를 순회하며 최솟값을 찾는 것입니다. 다만 두 수를 비교할 때 관계 연산자를 사용할 수 없으므로, 다음과 같은 아이디어를 활용합니다.

두 수를 동시에 1씩 감소시켜 먼저 0이 되는 쪽이 더 작은 수라는 원리입니다. 예를 들어 a = 3, b = 5일 때 두 값을 함께 줄이다 보면 a가 먼저 0이 되는데, 이는 a가 b보다 작다는 의미입니다. 이때 감소시킨 횟수가 곧 두 수 중 작은 값이 됩니다.

구현 코드

#include <iostream>
using namespace std;

// 관계 연산자 없이 두 수의 최솟값을 반환
int findMin(int a, int b) {
    int minVal = 0;
    while (a && b) {
        minVal++;
        a--;
        b--;
    }
    return minVal;
}

int findMinimumElement(int arr[], int n) {
    int minVal = arr[0];
    int i = (n - 1);
    while(i){
        minVal = findMin(minVal, arr[i]);
        i--;
    }
    return minVal;
}

int main() {
    int arr[] = {4, 2, 5, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The minimum element is "<<findMinimumElement(arr, n);
    return 0;
}

실행 결과

The minimum element is 1

동작 원리 정리

findMin 함수는 두 수 a, b가 모두 0이 아닌 동안(&&는 논리 연산자이므로 사용 가능) 두 값을 1씩 줄이면서 카운트를 증가시킵니다.
한쪽이 먼저 0이 되면 while 루프가 종료되고, 그 시점까지의 카운트가 두 수 중 작은 값이 됩니다.
findMinimumElement 함수는 배열의 마지막 요소부터 첫 번째 요소까지 순차적으로 findMin을 호출하여 전체 최솟값을 누적 계산합니다.

복잡도 분석

findMin의 반복 횟수는 두 수 중 작은 값에 비례하므로, 배열 요소의 값이 매우 클 경우 실행 시간이 오래 걸릴 수 있습니다. 따라서 시간 복잡도는 배열 요소 값의 크기에 의존하고, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.