비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
투 포인터 알고리즘
을 이용하였다.candidate
로 선언한다.sequence[s]
로 초기화한다.sum > k
=> sum에서 sequence[s]
를 빼고, s를 증가시킨다.sum < k
=> e를 증가시키고, sum에 sequence[e]
를 더한다.sum == k
=> candidate
배열에 현재 [s, e]
배열을 추가하고, s와 e를 각각 1씩 증가시킨다.e < sequence.length
일 동안 반복한다.function solution(sequence, k) {
var candidate = [];
// s는 시작인덱스, e는 끝인덱스
let s = 0,
e = 0;
let sum = sequence[0];
while(e < sequence.length) {
if(sum < k) sum += sequence[++e];
if(sum > k) sum -= sequence[s++];
if(sum == k) {
candidate.push([s, e]);
sum += sequence[++e];
sum -= sequence[s++];
}
}
// candidate를 부분수열의 사이즈가 작은 순서대로 정렬
candidate.sort((next, prev) => (next[1] - next[0]) - (prev[1] - prev[0]));
const filtered = candidate.filter(c => c[1] - c[0] === candidate[0][1] - candidate[0][0]).sort((next, prev) => next[0] - prev[0])
return filtered[0]
}