정수로 이루어진 배열이 주어졌을 때, 최대 한 개의 요소만 제거해서 엄격하게 증가하는(strictly increasing) 수열을 만들 수 있는지 확인하는 문제입니다.
여기서 수열 a0, a1, ..., an이 엄격하게 증가한다는 것은 a0 < a1 < ... < an을 만족한다는 의미입니다. 단, 요소가 하나뿐인 수열도 항상 엄격하게 증가하는 것으로 간주합니다.
문제 예시
예를 들어 sequence = [1, 3, 2, 1]이 주어진 경우 결과는 다음과 같습니다.
almostIncreasingSequence(sequence) = false
이 배열에서 어떤 요소를 하나 제거하더라도 엄격하게 증가하는 수열을 얻을 수 없습니다.
반면 sequence = [1, 3, 2]인 경우 결과는 다음과 같습니다.
almostIncreasingSequence(sequence) = true
배열에서 3을 제거하면 [1, 2]라는 엄격하게 증가하는 수열을 얻을 수 있습니다. 물론 2를 제거해서 [1, 3]을 만드는 방법도 가능합니다.
해결 아이디어
핵심은 배열을 앞에서부터 순회하면서 증가 규칙이 깨지는 지점의 개수를 세는 것입니다. 규칙이 깨지는 지점이 두 번 이상 나타나면 요소 하나의 제거만으로는 해결할 수 없으므로 false를 반환합니다.
알고리즘은 다음과 같이 동작합니다.
- 현재 요소가 이전 값(prev)보다 크면 수열이 정상적으로 유지되므로 prev를 갱신하고 계속 진행합니다.
- 현재 요소가 prev보다 작거나 같으면 규칙이 깨진 지점이므로 제거 횟수(removed)를 1 증가시키고, prev는 두 값 중 작은 값으로 갱신합니다. 이렇게 하면 뒤에 오는 요소와 비교할 때 더 유연하게 대응할 수 있습니다.
- 제거 횟수가 2 이상이 되면 반복을 종료하고, 최종적으로 removed < 2 여부를 반환합니다.
구현 코드
이를 JavaScript로 구현하면 다음과 같습니다.
const arr1 = [3, 5, 67, 98, 3];
const arr2 = [4, 3, 5, 67, 98, 3];
const almostIncreasingSequence = sequence => {
let removed = 0;
let i = 0;
let prev = -Infinity;
while(removed < 2 && i < sequence.length) {
if(sequence[i] > prev) {
prev = sequence[i];
} else {
prev = Math.min(prev, sequence[i]);
removed++;
}
i++;
}
return removed < 2;
};
console.log(almostIncreasingSequence(arr1));
console.log(almostIncreasingSequence(arr2));실행 결과
콘솔 출력 결과는 다음과 같습니다.
true false
arr1 = [3, 5, 67, 98, 3]의 경우 마지막 요소 3만 제거하면 [3, 5, 67, 98]이라는 엄격하게 증가하는 수열이 되므로 true입니다. 반면 arr2 = [4, 3, 5, 67, 98, 3]은 시작 부분의 역전(4 → 3)과 끝부분의 역전(98 → 3)이 모두 발생해 제거해야 할 요소가 두 개 이상이므로 false입니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용량은 O(1)로 매우 효율적입니다.