C++에서 조건 연산자와 비트 연산자 없이 4개 숫자 중 최댓값 구하기

문제 개요

이 문제에서는 네 개의 정수가 주어집니다. 목표는 C++에서 조건 연산자(if-else, 삼항 연산자 등)나 비트 연산자를 일절 사용하지 않고 네 숫자 중 최댓값을 찾는 프로그램을 작성하는 것입니다.

코드 설명

네 개의 정수 값이 주어졌을 때, 조건 분기나 비트 조작 없이 오직 산술 연산만으로 이 숫자들 사이의 최댓값을 구해야 합니다. 먼저 예제를 통해 문제를 이해해 보겠습니다.

입력

a = 4, b = 7, c = 1, d = 9

출력

9

해결 접근 방식

핵심 아이디어는 두 숫자씩 짝지어 비교하면서 더 큰 값을 골라내는 것입니다. 각 비교 단계에서 두 요소를 담은 2칸짜리 arr[] 배열을 만들고, 불리언 값을 배열 인덱스로 활용해 더 큰 요소를 반환합니다. 이 불리언 값은 다음 공식으로 계산됩니다.

[abs(x - y) + (x - y)]

이 식의 동작 원리는 매우 간단합니다.

• arr[0] > arr[1]인 경우 : (x−y)가 양수이므로 (x−y) + |x−y|의 결과는 0이 아닙니다. 여기에 NOT 연산(!)을 적용하면 False(0)가 되어 arr[0], 즉 더 큰 값이 반환됩니다.
• arr[0] < arr[1]인 경우 : 음수와 그 절댓값이 서로 상쇄되어 결과가 0이 됩니다. NOT 연산을 적용하면 True(1)가 되어 arr[1], 즉 더 큰 값이 반환됩니다.

즉, 불리언 값 자체가 "더 큰 값이 저장된 배열의 인덱스" 역할을 하므로 조건문 없이도 두 수의 최댓값을 얻을 수 있습니다. 이 함수를 이용해 첫 번째 숫자를 기준으로 나머지 세 숫자를 차례대로 비교하면 네 숫자의 전체 최댓값을 구할 수 있습니다.

솔루션 구현 예제

#include <iostream>
using namespace std;
int findMax(int x, int y){
    int arr[2] = {x,y};
    bool MaxIndex = ( !(arr[0] - arr[1] + abs(arr[0] - arr[1])));
    return arr[MaxIndex];
}
int CalcMaxElement(int a, int b, int c, int d) {
    int max = a;
    max = findMax(max, b);
    max = findMax(max, c);
    max = findMax(max, d);
    return max;
}
int main() {
    int a = 4, b = 9, c = 7, d = 1;
    cout<<"The maximum of four numbers is "<<CalcMaxElement(a,b,c,d);
    return 0;
}

출력

The maximum of four numbers is 9

코드 동작 원리 및 복잡도

findMax() 함수는 두 수의 차이에 그 절댓값을 더한 뒤 NOT 연산을 적용해 0 또는 1의 인덱스를 생성하고, 해당 인덱스의 배열 요소 즉 더 큰 값을 선택합니다. CalcMaxElement() 함수는 첫 번째 숫자 a를 초기 최댓값으로 설정한 뒤, b, c, d를 순서대로 findMax()에 전달하면서 최댓값을 갱신해 나갑니다.

비교 횟수는 고정적으로 세 번이며 각 비교는 상수 시간 안에 수행되므로 전체 시간 복잡도는 O(1)입니다. 추가적인 배열이나 자료구조 없이 상수 개수의 변수만 사용하므로 공간 복잡도 역시 O(1)입니다.