문제 정의
정수로 이루어진 배열이 주어졌을 때, 최대 한 개의 요소를 제거하여 남은 요소들이 엄격하게 증가하는 수열(strictly increasing sequence)이 되도록 만들 수 있는지 판별하는 문제입니다.
수열 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]을 만들어도 마찬가지입니다.
풀이 코드
아래는 그리디(greedy) 방식으로 문제를 해결하는 자바스크립트 코드입니다.
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));
코드 동작 원리
- removed: 지금까지 제거 처리한 요소의 개수입니다. 두 번 이상의 제거가 필요해지면 더 이상 조건을 만족하지 못합니다.
- prev: 직전까지의 유효한 마지막 값을 저장하며, 초기값은 음의 무한대(-Infinity)입니다.
- 현재 요소가 prev보다 크면 아직 수열이 증가 중이므로 prev를 갱신합니다.
- 현재 요소가 prev보다 작거나 같으면 순서가 어긋난 지점이므로 removed를 1 증가시키고, Math.min(prev, sequence[i])로 prev를 조정해 현재 요소를 남기는 쪽을 선택합니다.
- 반복이 끝난 뒤 removed가 2 미만이면 true, 그렇지 않으면 false를 반환합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
true false
첫 번째 배열 [3, 5, 67, 98, 3]은 마지막 요소 3만 제거하면 되므로 true가 반환되고, 두 번째 배열 [4, 3, 5, 67, 98, 3]은 앞부분(4 → 3)과 끝부분(98 → 3) 두 곳에서 순서가 어긋나므로 false가 반환됩니다.