정수들이 담긴 배열로 표현된 수열이 주어졌을 때, 최대 한 개의 요소만 제거해서 엄격하게 증가하는(strictly increasing) 수열을 만들 수 있는지 판별하는 문제를 살펴보겠습니다.
예를 들면 다음과 같습니다.
sequence = [1, 3, 2, 1]→ 결과는false입니다. 어떤 요소를 하나 제거하더라도 엄격하게 증가하는 수열을 만들 수 없습니다.sequence = [1, 3, 2]→ 결과는true입니다. 3을 제거하면[1, 2]가 되고, 대신 2를 제거하면[1, 3]이 되어 두 경우 모두 조건을 만족합니다.
엄격하게 증가하는 수열이란?
엄격하게 증가하는 수열은 수학 용어로, 모든 뒤따르는 숫자가 바로 앞의 숫자보다 반드시 커야 하는 수열을 의미합니다. 반면 일반적인 증가 수열은 뒤따르는 요소가 앞선 요소보다 '크거나 같기만' 하면 허용됩니다.
같은 논리는 감소 수열과 엄격하게 감소하는 수열에도 그대로 적용됩니다.
접근 방법
배열을 순회하면서 각 요소가 바로 다음 요소보다 작은지 확인합니다. 다음 요소가 더 크면 문제가 없지만, 그렇지 않은 경우 — 즉 arr[i] >= arr[i + 1]일 때는 엄격한 증가 조건을 위반한 것이므로 위반 횟수(unwantedElements)를 1씩 증가시킵니다.
순회 도중 위반 횟수가 1을 초과하면 그 자리에서 즉시 false를 반환하고, 배열 전체를 통과했을 때 위반 횟수가 1 이하라면 true를 반환하면 됩니다.
그럼 이 함수의 코드를 작성해 보겠습니다.
예제 코드
const isStrictlyIncreasing = (arr) => {
let unwantedElements = 0;
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] >= arr[i + 1]) {
unwantedElements++;
if (unwantedElements > 1) {
return false;
}
}
}
return true;
};
console.log(isStrictlyIncreasing([1, 3, 2, 1]));
console.log(isStrictlyIncreasing([1, 3, 2]));실행 결과
false true
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리는 O(1)로 매우 효율적입니다.
보너스: 단순 카운팅 방식의 한계 보완하기
위 코드는 단순히 위반 횟수만 세기 때문에 [3, 4, 2, 3]처럼 특정 위치의 요소를 정확히 골라 제거해야만 해결되는 경우를 올바르게 판별하지 못할 수 있습니다. 이럴 때는 앞뒤 요소를 비교해 어느 쪽을 제거할지 판단하도록 보완하는 것이 좋습니다.
const almostIncreasingSequence = (seq) => {
let bad = 0;
for (let i = 1; i < seq.length; i++) {
if (seq[i] <= seq[i - 1]) {
bad++;
if (bad > 1) return false;
// seq[i-1]을 제거할지, seq[i]를 제거할지 판단
if (seq[i] <= seq[i - 2] && seq[i + 1] <= seq[i - 1]) return false;
}
}
return true;
};
console.log(almostIncreasingSequence([3, 4, 2, 3])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true두 방식 모두 선형 시간 안에 동작하며, 코딩 테스트나 알고리즘 학습에서 자주 등장하는 유형이니 두 가지 접근 방법을 모두 익혀 두면 큰 도움이 됩니다.