[프로그래머스 lv2] 연속된 부분 수열의 합JS [투포인터]

https://school.programmers.co.kr/learn/courses/30/lessons/178870

 

---

 

문제 요점

• 비내림차순이란 222, 2334 처럼 <= 를 포함한 오름차순이란 뜻
• k가 되는 부분수열 중 최소 길이인 수열의 [첫 인덱스, 마지막 인덱스] 리턴
• 길이가 같은 수열이 여러개이면 인덱스가 작은 수열 리턴
• 5 ≤ sequence의 길이 ≤ 1,000,000 => nlogN

풀이

투포인터
시작 포인터와 끝 포인터 두 가지를 사용하면서 범위를 넓혀나간다.
포인터 사이의 모든 원소의 합이 k이하면 끝 포인터 값을 늘리고
k초과면 시작 포인터 값을 늘리기

 

• 포인터 i, j 둘 다 0인덱스에서 시작하고, j가 sequence 배열 끝에 다다를 때까지 순회하면서 합sum을 계산한다. (j가 sequence를 넘어가면 더 이상 큰 부분수열의 합을 구할 수 없다.)
• 둘의 합 = k 이면
  • answer에 {시작 인덱스, 끝 인덱스, 끝 인덱스-시작인덱스}를 저장한다
  • 가장 작은 수인 sequence[i]를 sum에서 빼고 새로운 부분수열을 찾기 위해 i 를 오른쪽으로 한 칸 이동한다.
• 둘의 합 < k 이면 다음으로 큰 수를 더한다
  •  j를 오른쪽으로 한 칸 이동, sum에 새로운 값을 더한다
• 둘의 합 > k이면 i 이면 가장 작은 수를 뺸다 
  • sum에서 기존의 i값을 빼고, i를 오른쪽으로 한 칸 이동한다.
• 순회를 마친뒤
  • 부분수열이 하나면 바로 리턴
  • 여러개이면 길이로 오름차순, 길이가 같다면 인덱스로 오름차순으로 정리한다.

 

 

 

 

function solution(sequence, k) {
    var answer = [];
    const len = sequence.length;
    let i = 0;
    let j = 0;
    let sum = sequence[0];
    
    // j sequence 마지막까지 순회한다.
    while(j < len) {
        if (sum === k) { // k를 찾음 answer에 추가하고 기존의 i값을 빼서 새로운 수열을 찾는다
            answer.push({i, j, len: j-i});
            sum -= sequence[i++];
        } else if (sum < k) { // k보다 작으면 다음으로 큰 수를 더한다
            sum += sequence[++j];
        } else if (sum > k) { // k보다 크면 가장 작은 수를 뺀다
            sum -= sequence[i++];
        } 
    }
    if (answer.length === 1) return [answer[0].i, answer[0].j]; // 부분수열이 하나면 바로 리턴
    // 여러개이면 길이로 오름차순, 길이가 같다면 인덱스로 오름차순
    answer.sort((a, b) => {
        if (a.len === b.len) {
            return a - b;
        } 
        return a.len - b.len;
    })
    return [answer[0].i, answer[0].j];
}

 

 

 

투포인터는 부분 탐색에 유용하다