🍀 연속된 부분 수열의 합

이 문제에서 누적합 알고리즘이 바로 떠오른 것은 죠르디를 매우 사랑하시는 김희성 개발자님의 재능기부 강의덕에 떠올랐다. 블로그를 쓰기 이전에 이 분에게 매우 감사드린다.ㅜㅜ🥺

누적합이라는 알고리즘을 이용하여 문제를 스스로 해결한 적은 처음이라 기록으로 남기려고 한다. 이 문제는 sequence를 for문을 두 번 돌리면 쉬울 거 같지만 시간 복잡도상으로 절대 통과할 수가 없다. 따라서 O(n)으로 줄이는 과정에서 누적합을 생각해 냈다.
전체적인 로직은 아래와 같다.

• sequence for문을 돌면서 처음 값부터 누적 합을 구한다.
  - 누적 합이 k보다 클 시 👉🏻 k보다 작거나 같을 때까지 누적합을 갱신한다.
  - 누적 합이 k와 같을 시 👉🏻 answer에 부분 수열 구간을 push한다.
• 문제의 조건에 맞게 부분 수열의 길이가 작으며 부분 수열의 처음 구간이 작은 것을 구한다.

logic을 보면 그리 어렵지 않겠지만, 무슨 소리인가 할 것 이다. 이는 코드를 이해한다면 이해가 갈 것이다.

1️⃣ Python

python으로 풀면서 다른 문제를 풀다가 min method를 어떤 기준으로 최소값을 찾을 수 있는 것을 보았다. 따라서 이를 익혀보기 위해 이 문제에서 적용했다.

how to use min method in python 👉🏻 여기

💡💡 min(iterable[, default=obj, key=func]) -> value

min method와 마찬가지로 max method또한 같은 방법으로 원하는 기준으로 최대값을 구할 수 있다.

def solution(sequence, k):
    answer = []
    acc_sum, start_idx = 0, 0
    
    for cur_idx, curNum in enumerate(sequence):
        acc_sum += curNum
        
        if acc_sum > k:
            while acc_sum > k:
                acc_sum -= sequence[start_idx]
                start_idx += 1
                
        if acc_sum == k: 
            answer.append([start_idx, cur_idx])
    
    return min(answer, key = lambda arr: arr[1] - arr[0])

return문에 key값에 구간 길이를 기준으로 최소인 배열을 return하도록 한 것이다.

2️⃣ Javascript

Javascript는 sortKey라는 함수를 따로 만들어서 문제의 조건을 충족시켰다. 정렬을 한 후 맨 앞의 값을 return 하도록 했다.

// sortKey function
function sortKey(a, b){
    // 구간의 길이가 같다면 index가 짧은 순으로 오름차순 정렬
    if (a[1] - a[0] === b[1] - b[0]){
        return a[0] - b[0];
    }
    
    // 구간의 길이가 짧은 순으로 오름차순 정렬
    return (a[1] - a[0]) - (b[1] - b[0])
}

// solution
function solution(sequence, k) {
    let [accSum, startIdx] = [0, 0];
    
    const partial_permutations = sequence.reduce((acc, curNum, curIdx) => {
        accSum += curNum;
        
        if (accSum > k){
            while (accSum > k){
                accSum -= sequence[startIdx];
                startIdx += 1;
            }
        }
        
        if (accSum === k) acc.push([startIdx, curIdx]);
        
        return acc;
    }, [])
    
    return partial_permutations.sort(sortKey)[0];
}

항상 느끼는 거지만 reduce는 정말 만능인 것 같다. python에도 reduce라는 함수는 존재하는데 functool library에서 import 해와야 한다. 👉🏻 python reduce docs

from functools import reduce

🚀 마치며

일단, 요새 알고리즘을 계속 푸는데 실력이 느는 것이 체감되어서 기분이 매우 좋다. 이전에 앞서 서론에 언급한 감사드린 분의 강의를 다른 것 때문에 바빠서 줌을 그 때 그 때 참석하지 못했지만, 남겨진 자료를 통해 공부하면서 정말 많은 생각이 바뀐 것 같다. 단지 문제를 풀기 위해 알고리즘을 공부하면서 스트레스 아닌 스트레스를 받았는데 요새는 재밌다... 누가 그랬는데 무엇이던 생각보다 잘해지면 재밌어진다는......;; 더 열심히 풀어서 프로그래머스 level3문제정도는 뿌셔뿌셔하는 것이 내 목표이다. 홧팅!!🔥🔥🔥