[프로그래머스/level2/JS] 연속된 부분 수열의 합

문제링크

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

문제풀이

조건에 맞춰 부분 수열의 합을 구했을 때 수열의 인덱스를 구하는 문제이다.

 

우선 조건을 보도록 하자.

 

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

=> 우선 비내림차순으로 정렬된 수열이 주어진다고 한다. 비내림차순? 오름차순이라는 말이 있는데 왜 비내림차순이라고 할까? 해서 찾아봤더니 오름차순은 뒤의 원소가 항상 커져야하지만 비내림차순은 같을 수도 있는 경우를 이야기한다고 한다. 그러면 인덱스가 커질 때 같거나 그 이상의 원소가 온다는 것을 알수 있다.

 

1. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분수열이어야 합니다.

=> 말이 장황하게 되어있는데 수열과 인덱스 두개가 주어질 때 해당 인덱스를 포함하여 만들어지는 수열이다. 똑같이 말하는 것 같지만 예시를 보는 것이 더 쉬울 것 같다.

예를 들어 수열: [1, 5, 7, 8, 9, 9]과 인덱스: [2, 4]이 주어질 때 2와 4를 포함하는 인덱스 즉 2, 3, 4인덱스의 값으로 만들어지는 부분수열 [7, 8, 9]를 이야기한다.

 

2. 부분 수열의 합은 k입니다.

=> 부분 수열의 합이 k가 되어야 한다고 한다.

 

3. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.

=> 합이 k가 되는 부분 수열 중 길이가 짧은, 즉 인덱스의 차이가 작은 수열을 찾으라고 한다.

 

4. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

=> 만약 인덱스의 차이가 같다면, 앞의 인덱스가 작은 수열이 우선이라고 한다.

 

정답이 되는 부분 수열을 구하는 조건은 위와 같고 그렇다면 제한 사항을 알아보자.

 

1. 5 <= sequence의 길이 <= 1,000,000

2. 1 <= sequence의 원소 <= 1,000

3. 5 <= k <= 1,000,000,000

그리고 sequence는 앞에서 이야기했듯이 비내림차순 수열이며 항상 합이 k가 되는 부분 수열을 만들수 있다고 한다.

 

여기서 중요한 부분은 sequence의 길이, 비내림차순 수열, 항상 합이 k가 되는 부분 수열을 만들수 있다는 부분인 것 같다.

 

우선 완전탐색을 생각해보면 sequence의 길이가 10^6이므로 길이가 1인 부분 수열 10^5개, 길이가 2인 부분 수열 10^5 - 1개, 길이가 3인 부분 수열 10^5 - 2개 ... 길이가 10^5인 부분 수열 1개. 가우스의 1부터 100까지 수를 더하는 방식으로 계산하면

(1 + 10^5) * (10^5 / 2) => O(10^10)... 시간초과가 남을 알 수 있다.

 

그렇다면 완전탐색을 제외하고 잔머리를 굴려야한다. 수열이 비내림차순이라고 하였다. 우리는 합이 k가 되는 부분 수열을 찾아야 한다. 그리고 부분 수열의 합이 k보다 작을 수 있고, k가 될 수도 있고, k보다 클 수 있다. 그것이 부분 수열이니까.

 

그것이 부분 수열의 합이니까

그렇다면 부분 수열은 연속된 인덱스로 구성되므로 부분 수열의 합이 k보다 작다면 앞의 인덱스를 하나 더해주고, k보다 크다면 뒤의 인덱스를 하나 더해주고 합을 유지하는 방식, 즉 투포인터 방식으로 풀면 해결할 수 있을 것 같다.

 

그리고 4번 조건에서 길이가 짧은 수열이 여러 개라면 시작 인덱스가 작은 것이 우선 순위가 높으므로 만약 합이 k일 때 인덱스의 차이가 같다면 답을 갱신 시켜줄 필요는 없고 인덱스의 차이가 작은 경우에만 답을 갱신시켜주면 될 것 같다.

 

코드

function solution(sequence, k) {
    let answer = [0, sequence.length - 1];
    
    let start = 0;
    let end = -1;
    let currentSum = 0;
    
    while(start < sequence.length && end < sequence.length) {
    	// index가 하나라도 length를 넘어가면 종료
        
        if(currentSum < k) {
        	// 부분 수열의 합이 k보다 작은 경우, 인덱스 뒤 증가
            end++;
            currentSum += sequence[end];
        } else if (currentSum === k) {
        	// 부분 수열의 합이 k인 경우, 이전 인덱스 길이와 비교
            const currentLength = end - start;
            const preLength = answer[1] - answer[0];
            
            if(currentLength < preLength) answer = [start, end];
            
            // 이후 인덱스 앞 증가
            currentSum -= sequence[start];    
            start++;
        } else if (currentSum > k) {
        	// 부분 수얄의 합이 k보다 큰 경우, 인덱스 앞 증가
            currentSum -= sequence[start];
            start++;
        }
    }
    
    return answer;
}

 

설명에 오류가 있거나 궁금한 부분이 있으면 언제든지 댓글로 달아주세요!

읽어주셔서 감사합니다.