프로그래머스 코딩테스트 연습 - 연속된 부분 수열의 합 JavaScript

연속된 수열에서 부분 수열의 합이 원하는 값을 충족하는 경우가 있는지 확인하는 문제였다.

당연히 이중 for문을 사용하면 문제를 해결할 수 있지만, 정답은 아닐 것이라고 생각했다.

문제 조건에 합을 만족해도, 여러 경우의 수가 있다면 가장 짧은 부분수열을 구해야 했기에 큰 수부터 더해가는 접근법을 생각했다.

function solution(sequence, k) {
    let start = sequence.length - 1;
    let end = sequence.length - 1;
    let sum = sequence[start];
    while(start > 0) {
        if(sum === k) {
            break;
        } else if(sum > k) {
            sum -= sequence[end];
            end--;
        } else {
            sum += sequence[start - 1];
            start--;
        }
    }
    return [start, end];
}

위와 같은 코드를 작성하였는데, 여전히 문제는 있었다.

문제의 조건인 부분수열의 길이가 같은 여러 정답이 있을 땐, 앞의 인덱스부터 설정된 부분수열을 반환해야 한다.

위에서 짧은 부분 수열을 만들기 위해서 뒤의 큰 숫자부터 접근한 것이 컸다.

 

이 경우를 케어하여 문제를 해결할 수 있었다.

여전히 뒤에서 부터 접근하지만, 이번에는 정답이 나와도 비교를 계속하여 start가 0이 될 때까지 계속 정답을 확인하는 로직을 추가했다.

function solution(sequence, k) {
    let start = sequence.length - 1;
    let end = sequence.length - 1;
    let sum = sequence[start];
    let answer = false;
    while(start >= 0) {
        if(sum === k) {
            if(answer && answer[1] - answer[0] > end - start) {
               break;
            }
            if(!answer || answer[1] - answer[0] >= end - start){
               answer = [start, end];
            }
        } 
        if(sum >= k) {
            sum -= sequence[end];
            end--;
        } else {
            sum += sequence[start - 1];
            start--;
        }
    }
    return answer;
}

역시 문제를 푸는데 있어서 예외처리나 예상치 못한 결과값을 고려하는 부분이 가장 어려운 것 같다.