Level 2️⃣ - 연속된 부분수열의 합(Feat. 투포인터)

투포인터

투 포인터와 관련된 기본 문제는 아래 링크에 정리해두었다.

문제에서도 언급되지만 정렬이 되어있다는 조건을 잘 확인하자. 

https://ukgi-dev.tistory.com/16

투 포인터 알고리즘 - 개념정리

 

🚀문제 접근

무식하게 접근하는 방법이 있다. 물론 처음에는 이 방법도 생각나지 않았지만...

2

3

6

5

1

 

2가 맨 앞에 올 때 연속 부분수열, 3이 맨 앞에 올 때 연속 부분수열, 6이 맨 앞에 올 때 연속 부분수열 ...

이렇게 이중 for문을 돌려서 구할 수 있지만 데이터가 커지면 O(n^2) 시간복잡도를 가지기 때문에 실패하는 경우가 많다.

밑에는 이중 for문으로 구현한 코드이다.

아래 코드를 구현한 이유는 왜 투포인터 알고리즘이 효율성을 가지는지 확실히 배우기 위해서 구현해보았다.

그리고 이 문제는 투포인터를 사용하라는 힌트를 많이 준 문제이다. 연속 부분수열이면서 정렬된 배열이 데이터로 주어지고 연속 부분수열의 인덱스를 반환해야하기 때문이다.

function solution(sequence, k) {
    let ret = [];
    for(let i = 0; i<sequence.length; i++){
        let tmp = [];
        let sum = sequence[i];
        tmp.push(i);
        if(sum === k){
            ret.push(tmp);
            continue;
        }
        else if(sum > k) continue;
        for(let j = i+1; j<sequence.length; j++){
            tmp.push(j);
            sum += sequence[j];
            if(sum === k){
                ret.push(tmp);
                break;
            }
            else if(sum > k) break;
        }
    }
    ret.sort((a,b)=> {
        if(a.length === b.length) return a[0] - b[0];
        return a.length - b.length;
    });
    
    return [ret[0][0], ret[0][ret[0].length - 1]];
}

 

🎯투포인터로 구현하기

function solution(sequence, k) {
    let ret = [];
    let sum = 0;
    let n = sequence.length;
    let left = 0;
    let right = 0;
    while(right <= n){
        if(sum === k){
            ret.push([left, right - 1]);
            sum -= sequence[left++];
        };
        if(sum > k) sum -= sequence[left++];
        if(sum < k) sum += sequence[right++];
    }
    ret.sort((a,b)=>{
        if((a[1] - a[0]) === (b[1] - b[0])) return a[0] - b[0];
        return (a[1] - a[0]) - (b[1] - b[0]);
    });
    return ret[0];
}

 

이 코드에서 주의해야할 점 두 가지를 짚어본다.

 

위 코드에서 sum은 right 포인터까지의 합이 아니라 right 포인터 직전까지의 합을 나타내고 있다.

그렇기 때문에 인덱스를 저장할 때는 right에 1을 꼭 빼주어야한다.

 

그리고 또 다른 하나는 while문의 기저조건이다.

right <= n 인 경우 포인터 탐색을 중단하게 되어있는데 맨 처음에는 right < n이라고 생각했지만,

직접 시뮬레이션을 해보니 마지막 요소가 k를 만족하는 경우에는 포함시키지 않고 있었다.

따라서 right는 sequence의 길이까지는 가야한다. 이 부분은 직접 입력 예시를 적용해보면 금방 알 수 있다.