문제 설명
오름차순(증가 순서)으로 정렬된 숫자 배열이 하나 주어집니다. 그런데 이 배열에는 단 하나의 요소만 정렬 순서에서 벗어나 있습니다. 우리가 작성해야 할 JavaScript 함수는 바로 그 요소를 찾아 반환하는 역할을 합니다.
예를 들어 [1, 2, 3, 4, 17, 5, 6, 7, 8]과 같은 배열이 입력으로 들어온다면, 대부분의 값은 오름차순을 유지하고 있지만 17만 순서에서 어긋나 있으므로 함수는 17을 반환해야 합니다.
접근 방법
배열을 처음부터 순회하면서 인접한 세 요소 간의 관계를 검사하면 됩니다. 완전한 오름차순 배열이라면 항상 다음 조건이 성립해야 합니다.
- 현재 요소가 다음 요소보다 작거나 같아야 함 →
arr[i] <= arr[i + 1] - 다음 요소도 그다음 요소보다 작거나 같아야 함 →
arr[i + 1] <= arr[i + 2]
따라서 현재 요소와 다음 요소의 차이가 음수(정상적인 증가)인데, 다음 요소와 그다음 요소의 차이가 양수(감소)라면 arr[i + 1]이 바로 순서에서 벗어난 요소입니다.
구현 코드
const arr = [1, 2, 3, 4, 17, 5, 6, 7, 8];
const findWrongNumber = (arr = []) => {
for (let i = 0; i < arr.length - 2; i++) {
const el = arr[i];
if (el - arr[i + 1] < 0 && arr[i + 1] - arr[i + 2] > 0) {
return arr[i + 1];
}
}
};
console.log(findWrongNumber(arr));출력 결과
17
코드 설명
함수 내부의 조건식을 살펴보면 다음과 같습니다.
el - arr[i + 1] < 0: 현재 요소가 다음 요소보다 작다는 의미로, 이 구간 자체는 아직 정상적인 증가 상태입니다.arr[i + 1] - arr[i + 2] > 0: 다음 요소가 그다음 요소보다 크다는 의미로, 여기서 감소가 발생했음을 나타냅니다.
두 조건이 동시에 참이 되는 지점의 arr[i + 1], 즉 증가 흐름을 깨뜨리는 값이 곧 찾고자 하는 어긋난 요소입니다. 위 예제에서는 4 다음에 위치한 17이 이 조건을 만족하므로 17이 반환됩니다.
참고로 반복문의 범위를 arr.length - 2까지로 설정하면 마지막 반복에서 존재하지 않는 arr[i + 2]에 접근하는 것을 방지할 수 있어 더욱 안전한 코드가 됩니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다.