[프로그래머스>LV2] 연속된 부분 수열의 합 (Kotlin, Python)

프로그래머스

 

1. 문제

[입력]

• 수열을 나타내는 정수 배열 sequence
• 부분 수열의 합을 나타내는 정수 k

[결과]

조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return

 

2. 풀이

알고리즘 문제 중에 잘 알려진 최대 연속 부분 수열의 합으로 생각하고 풀면 큰일나는 문제입니다.ㅎㅎ

 

조건 중에

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

에서 알 수 있듯이, 해당 문제는 부분 수열을 띄엄띄엄 만드는 것이 연속된 부분 수열들로 이루어진다는 것에 유의하셔야 합니다.

 

이를 통해 이 문제는 투 포인트를 사용해 풀 수 있다는 것을 알 수 있습니다. 🤗

 

3. 코드

Kotlin

class Solution {
    fun solution(sequence: IntArray, k: Int): IntArray {
        var answer: IntArray? = null
        val n = sequence.size
        var minLength = n
        var maxSum = sequence.first()
        var left = 0
        var right = 1

        while (left < right) {
            val length = right - left
            if (maxSum == k && minLength > length) {
                minLength = length
                answer = intArrayOf(left, right - 1)
            }
            if (maxSum <= k && right < n) {
                maxSum += sequence[right]
                right += 1
            } else {
                maxSum -= sequence[left]
                left += 1
            }
        }

        return answer ?: intArrayOf(0, n - 1)
    }
}

 

Python

def solution(sequence, k):
    answer = []
    
    n = len(sequence)
    # 부분수열의 길이, 부분수열의 합
    min_len, max_sum = n, sequence[0]
    left, right = 0, 1
    
    while left < right:
        length = right - left
        if min_len > length and max_sum == k:
            answer = [left, right-1]
            min_len = length
        if max_sum <= k and right < n:
            max_sum += sequence[right]
            right+=1
        else:
            max_sum -= sequence[left]
            left+=1
            
    if answer == []: return [0,n-1]
    return answer