문제 정의
정렬된 정수 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 배열을 하나 이상의 부분 시퀀스(subsequence)로 나눌 수 있고, 각 부분 시퀀스가 연속된 정수로 구성되며 길이가 최소 3 이상일 경우에만 true를 반환하고, 그렇지 않다면 false를 반환해야 합니다.
예를 들어, 함수의 입력이 다음과 같다고 가정해 보겠습니다.
입력
const arr = [1, 2, 3, 3, 4, 5];
출력
const output = true;
출력 설명
이 배열은 아래와 같이 두 개의 연속 부분 시퀀스로 나눌 수 있습니다.
1, 2, 3
3, 4, 5
접근 방법: 탐욕적(Greedy) 알고리즘
이 문제는 탐욕적 접근 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- count 객체: 배열에 있는 각 숫자의 남은 개수를 저장합니다.
- needed 객체: 기존 시퀀스를 확장하기 위해 특정 숫자가 필요하다는 사실을 추적합니다. 예를 들어 지금까지 만든 시퀀스가
1, 2, 3으로 끝난다면, 다음에4가 등장하면 이 시퀀스에 붙이는 것이 새로운 시퀀스를 만드는 것보다 유리합니다.
각 숫자를 순서대로 처리할 때 세 가지 경우를 고려합니다.
- 기존 시퀀스가 현재 숫자를 기다리고 있다면(
needed[num]이 존재), 해당 시퀀스를 확장하고 다음 숫자(num + 1)를 필요 목록에 추가합니다. - 그렇지 않고 현재 숫자 뒤에 올 두 개의 연속 숫자(
num + 1,num + 2)가 모두 남아 있다면, 길이 3짜리 새로운 시퀀스를 시작하고 그 뒤 숫자(num + 3)를 필요 목록에 추가합니다. - 위 두 조건이 모두 불가능하면 해당 숫자를 어느 유효한 시퀀스에도 배치할 수 없으므로 즉시
false를 반환합니다.
예시 코드
다음은 위 로직을 구현한 전체 코드입니다.
const arr = [1, 2, 3, 3, 4, 5];
const canSplit = (arr = []) => {
// 각 숫자의 빈도수를 계산
const count = arr.reduce((acc, num) => {
acc[num] = (acc[num] || 0) + 1
return acc
}, {})
// 기존 시퀀스가 다음으로 필요로 하는 숫자 추적
const needed = {}
for (const num of arr) {
// 이미 사용한 숫자는 건너뜀
if (count[num] <= 0) {
continue
}
count[num] -= 1
// 1) 기존 시퀀스를 확장할 수 있는 경우
if (needed[num] > 0) {
needed[num] -= 1
needed[num + 1] = (needed[num + 1] || 0) + 1
// 2) 길이 3짜리 새 시퀀스를 시작할 수 있는 경우
} else if (count[num + 1] > 0 && count[num + 2]) {
count[num + 1] -= 1
count[num + 2] -= 1
needed[num + 3] = (needed[num + 3] || 0) + 1
// 3) 어느 쪽도 불가능한 경우
} else {
return false
}
}
return true
}
console.log(canSplit(arr));
출력 결과
true
동작 원리 요약
입력 [1, 2, 3, 3, 4, 5]를 단계별로 살펴보면 다음과 같습니다.
1처리: 대기 중인 시퀀스가 없고,2와3이 남아 있으므로 새 시퀀스1, 2, 3을 시작하고4를 필요 목록에 추가합니다.2,3처리: 이미 앞선 시퀀스 생성 시 소비되었으므로 건너뜁니다.- 두 번째
3처리: 대기 중인 시퀀스가 없지만4와5가 남아 있으므로 새 시퀀스3, 4, 5를 시작하고6을 필요 목록에 추가합니다. 4,5처리: 이미 소비되었으므로 건너뜁니다.
모든 숫자가 성공적으로 배치되었으므로 최종 결과는 true입니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 공간 역시 숫자 종류에 비례하는 O(n)입니다.