Question

js 정답 및 짧은 해설

저도 고수가 아니지만 공부하는 분들 위해 올려봅니다.

sequence의 요소가 100만개 이기 때문에 매 순간마다 부분수열의 합을 구하는 2중 for문을 사용하는 방법으로
문제를 풀 경우 시간초과를 맞이하게 됩니다. (시간복잡도 O(N²⁾⁾

따라서 우리는 부분수열의 합을 구할때 좀 더 효율적인 O(N)이나 O(NlogN)의 풀이를 생각해야합니다.

누적합 스킬을 사용해봅시다. 새로운 문제로 예를 들어보겠습니다.

arr = [1,2,3,4,5] 가 주어졌을때 arr.slice(2,5)의 모든요소의 합을 구하여라.

[3,4,5] => 3+4+5 = 12 　　　　　　　　　　　　　　　　　　 // 　　 문제의 답을 이렇게 표현 할 수도 있지만
( [1,2,3,4,5] 의 합 ) - ( [1,2] 의 합) => 15 - 3 = 12 　　　　　　　 // 　　 이렇게도 표현할 수 있으며
( arr.slice(0,5) 합 ) - ( arr.slice(0,2) 의 합 )= 12 　　　　　　　　 // 　　 정리하면 이렇게 됩니다.

여기서 누적합 배열 prefix = [0, 1, 3, 6, 10, 15] 를 우리가 만들어놓는다면
정답은 prefix[5] - prefix[2] 로 표현할 수 있습니다.

이 특성을 이용하여 이제 우리는 arr의 길이가 100만이고 구해야하는 부분수열의 합의 갯수가 100만개라도 O(N)으로 해결가능해졌습니다.

아래는 누적합, 투포인터를 사용한 정답 코드입니다.

작성중인 코드―solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function solution(sequence, k) {
    var answer = [];
    let prefix = [0]       // sequence의 합을 나타낸 배열
    let maxL  = Infinity   // 정답으로 나온 부분수열의 길이를 나타내는 변수 
    sequence.forEach((num,i)=>{
        prefix.push(num+prefix[i])
    })

    // prefix[i]에는 sequence[0]부터 sequence[i-1] 요소까지의 합이 들어있다.
    // ex) sequence = [1, 2, 3, 4, 5] , prefix = [0, 1, 3, 6, 10, 15]

    let left = 0
    let right = 0

    // 투포인터 시작. 
    // 현재까지의 합이 K보다 작으면 right를 +1씩 올린다.
    // 아니라면 left를 +1씩 올린다.
    while(left<=right){
        let sum = prefix[right] - prefix[left]  // sequence[left] 부터 sequence[right-1]까지의 수열의 합.
        if(sum === k) {
            // 정답수열을 찾았을때 수열의 길이를 체크하고 가장 작은길이의 수열로 변환. 
            let nowL = right-1 - left 
            if(maxL > nowL){
                answer = [left,right-1]
                maxL = nowL
            }
        }
        if(sum<k){
            right++
        }else left++
    }

    return answer;
}

박상현

2023.4.7 00:30

js 정답 및 짧은 해설

누적합 스킬을 사용해봅시다. 새로운 문제로 예를 들어보겠습니다.

arr = [1,2,3,4,5] 가 주어졌을때 arr.slice(2,5)의 모든요소의 합을 구하여라.

작성중인 코드―solution.js

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.