이 문제에서는 양수로만 이루어진 크기 n의 배열 arr[]가 주어집니다. 우리의 과제는 관계 연산자(비교 연산자)를 사용하지 않고 배열에서 최댓값을 찾는 것입니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력: arr[] = {5, 1, 6, 7, 8, 2}
출력: 8
해결 접근 방법
관계 연산자(>, <, >=, <= 등)를 사용하지 않고 두 값을 비교하려면 다른 방식으로 접근해야 합니다. 여기서 활용할 수 있는 핵심 아이디어는 반복적인 감산(repeated subtraction)입니다.
두 수를 동시에 1씩 계속 빼다 보면, 더 작은 수가 먼저 0에 도달하고 더 큰 수가 나중에 0에 도달합니다. 즉, 0까지 도달하는 데 더 오래 걸리는 수가 바로 더 큰 값입니다.
구체적인 알고리즘은 다음과 같습니다.
- 배열의 첫 번째 요소를 초기 최댓값으로 설정합니다.
- 두 값을 비교할 때마다 두 수를 동시에 1씩 감소시켜 모두 0이 될 때까지 반복합니다.
- 0이 되기 전까지 감소 횟수를 세면, 그 값이 두 수 중 더 큰 값이 됩니다.
- 이 방식으로 배열의 나머지 요소들을 순차적으로 현재 최댓값과 비교하여 전체 배열의 최댓값을 구합니다.
솔루션 구현 코드
위 접근 방식을 C++ 코드로 구현한 예제입니다.
#include <iostream>
using namespace std;
// 관계 연산자 없이 두 수 중 큰 값을 반환하는 함수
int returnMax(int x, int y) {
int c = 0;
// x 또는 y가 0이 아닐 때까지 반복
while(x || y) {
if(x)
x--;
if(y)
y--;
c++;
}
return c;
}
// 배열 전체에서 최댓값을 찾는 함수
int findMaxEle(int A[], int N) {
int maxVal = A[0];
for (int i = N-1; i; i--)
maxVal = returnMax(maxVal, A[i]);
return maxVal;
}
int main() {
int A[] = {5, 1, 6, 7, 8, 2};
int N = sizeof(A) / sizeof(A[0]);
cout << "배열의 최댓값은 " << findMaxEle(A, N);
return 0;
}실행 결과
배열의 최댓값은 8
코드 설명 및 시간 복잡도
returnMax 함수: 두 정수 x와 y를 받아 while 루프 안에서 두 값을 동시에 1씩 감소시킵니다. 반복문이 종료되었을 때 카운터 c에는 두 수 중 큰 값이 저장되어 있습니다. 예를 들어 x=5, y=8이라면, 5번째 반복 후 x가 먼저 0이 되고, 8번째 반복 후 y도 0이 되면서 c는 8이 됩니다.
findMaxEle 함수: 배열의 마지막 요소부터 시작해 각 요소를 현재 최댓값과 비교하며 returnMax를 호출합니다. 모든 요소를 비교한 후 최종 최댓값을 반환합니다.
시간 복잡도: 이 방법은 단순 비교 연산자를 사용하는 O(N) 방식과 달리, 값의 크기만큼 반복문이 실행되므로 시간 복잡도는 O(N × M)입니다. 여기서 N은 배열의 크기, M은 배열 내 최댓값의 크기를 의미합니다. 따라서 이 기법은 알고리즘 학습 및 인터뷰용 문제로 적합하며, 실제 성능이 중요한 환경에서는 권장되지 않습니다.