이번 문제에서는 숫자 배열을 입력받아 두 요소 사이의 최대 차이를 구하는 JavaScript 함수를 작성해야 합니다. 단, 중요한 조건이 있습니다. 더 작은 값이 반드시 더 큰 값보다 배열의 앞쪽에 위치해야 한다는 점입니다. 즉, "먼저 나온 낮은 값"과 "그 이후에 나온 높은 값"의 차이만 유효합니다.
문제 이해하기
다음과 같은 배열을 살펴보겠습니다.
const arr = [2, 5, 6, 12, 1];
이 배열에 대해 함수는 10을 반환해야 합니다.
배열 전체에서 가장 큰 값은 12, 가장 작은 값은 1입니다. 하지만 1은 12보다 뒤에 등장하기 때문에, 이 문제의 조건에서는 유효한 "작은 값"으로 간주할 수 없습니다.
따라서 함수가 계산하는 차이는 다음과 같습니다.
12 - 2 = 10
해결 접근 방식
이 문제는 배열을 한 번만 순회하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 왼쪽에서 오른쪽으로 순회하면서 지금까지 만난 최솟값(min)을 계속 추적합니다.
- 현재 요소가 min보다 크다면, 두 값의 차이를 계산해 기존 최대 차이(diff)보다 큰지 확인하고, 더 크면 갱신합니다.
- 현재 요소가 min보다 작거나 같다면, min을 현재 요소로 갱신합니다.
구현 코드
const arr = [2, 5, 6, 12, 1];
const findLargestDifference = (arr = []) => {
if (arr.length <= 1){
return -1;
};
let min = arr[0];
let diff = 0;
for (let i = 1; i < arr.length; i++) {
if (arr[i] > min && (arr[i] - min > diff)) {
diff = arr[i] - min;
}
else if (arr[i] <= min) {
min = arr[i];
}
}
if (diff <= 0){
return -1
};
return diff;
};
console.log(findLargestDifference(arr));
코드 설명
- 길이 검사: 배열의 길이가 1 이하라면 비교할 요소 쌍이 존재하지 않으므로 -1을 반환합니다.
- min 초기화: 첫 번째 요소를 초기 최솟값으로 설정합니다.
- 순회: 두 번째 요소부터 마지막 요소까지 순회하면서, 현재 값이 min보다 크면 차이를 계산해 diff를 갱신하고, 그렇지 않으면 min을 새로운 최솟값으로 업데이트합니다.
- 결과 판정: 순회가 끝난 후 diff가 0 이하라면(즉, 조건을 만족하는 증가하는 쌍이 없었다면) -1을 반환합니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
10
시간 복잡도
이 알고리즘은 배열을 단 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용량은 O(1)입니다. 참고로 이 패턴은 주식 가격이 담긴 배열에서 최대 이익을 구하는 고전적인 문제와 동일한 유형으로, 코딩 인터뷰에서 자주 출제되는 주제이기도 합니다.