[투포인터] 프로그래머스 '연속된 부분 수열의 합' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드) 타임아웃. 이번에는 해결해보려고 별 짓을 다했다 ㅋㅋㅋ 나름..내선에서..

function solution(sequence, k) {
    let candidate = [];
    let min = 999996;
    let sum = 0;
    
    for(let i=sequence.length-1;i>=0;i--){
        sum += sequence[i];
        if(sum === k) {
            candidate.push([i,i]);
            min = 0;
        }else{
            for(let j=i-1;j>=0;j--){
                sum += sequence[j];
                if(sum === k){
                    candidate.push([j,i]);
                    if(i-j < min) min = i-j; 
                    break;
                }
            }
        }
        sum = 0;
    }
    
    for(let i=candidate.length-1;i>=0;i--){
        if(candidate[i][1] - candidate[i][0] === min) 
            return candidate[i];
    }
    
}

정답) 

이 방식은 포인터(이것도 슬라이딩 윈도우라고 하나..?) + 1중 for문을 사용하는 방식이다. 2중 for문이 아니라 그런가.. 시간이 무지하게 줄었다.

function solution(sequence, k) {
    let answer = []; // 정답이 될 수 있는 후보를 담을 배열
    let sum = 0; 
    let head = 0; // 포인터
    let min = sequence.length;
    let result = []; // 답
    
    for(let i = 0; i<sequence.length;i++){
        sum += sequence[i];
        if(sum > k){
          // 작아질 때까지 앞에 값을 빼줌
            while(sum > k){
                sum -= sequence[head++];
            }
        }
        if(sum===k){ // k와 같다면 후보에 추가
            answer.push([head,i]);
        }
    }
    
    answer.forEach((el)=>{
        if(min > el[1] - el[0]){
            min = el[1] - el[0];
            result = [el[0],el[1]];
        }
    }) 
    
    return result;
}

 

이해에 도움이 된 블로그)

https://velog.io/@sean2337/Programmers-%EC%97%B0%EC%86%8D%EB%90%9C-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A9-JavaScript

[Programmers] 연속된 부분 수열의 합 - JavaScript

투포인터로 푸는 방법도 있다. 또 너냐 투포인터? 투포인터는 개념은 간단한데 문제를 보고 이걸 투포인터로 풀어야겠다는 생각이 안드는게 문제다!!! 난도 높은 문제들에 많이 나오던데...

https://sasca37.tistory.com/319

[프로그래머스] - 연속된 부분 수열의 합 (Java & JavaScript)

 

복기

6/22