[JS] 연속된 부분 수열의 합

 

 

난이도: Lv. 2

정답률: 51%

문제: https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

 

알고리즘

1. sequence의 첫 번째 값을 sum에 저장하고, 시작 인덱스와 끝 인덱스를 0으로 지정한다.
2. sum과 k의 관계에 따라 시작 인덱스와 끝 인덱스를 조정한다. 끝 인덱스가 sequence 배열의 끝에 도달할 때까지 반복한다.
   1. sum이 k보다 작을 경우 끝 인덱스를 1 증가시키고 그 인덱스에 해당하는 값을 sum에 더한다.
   2. sum이 k보다 클 경우 시작 인덱스에 해당하는 값을 sum에서 빼고, 시작 인덱스를 1 증가시킨다.
   3. sum과 k가 같을 경우 현재 정답으로 되어있는 시작 인덱스와 비교하여 시작 인덱스가 더 작은 것을 정답으로 기록한다.

 

 

코드

function solution(sequence, k) {
    let answer = [0, 1000000];
    let startIdx = 0, endIdx = 0;
    let sum = sequence[0];
    while (endIdx < sequence.length) {
        if (sum < k) {
            sum += sequence[++endIdx];
        } else if (sum > k) {
            sum -= sequence[startIdx++];
        } else {
            if (answer[1] - answer[0] > endIdx - startIdx) {
                answer = [startIdx, endIdx];
            }
            sum += sequence[++endIdx];
        }
    }

    return answer;
}

 

 

주저리

분명 어려운 문제가 아닌데 내 능력 부족이고 창의력 부족이다........... 도저히 갈피를 못 잡겠어서 질문하기 들어갔다가 제목에 투 포인터라고 적힌 거 보고는 내용 안 보고 다시 문제로 돌아와서 sequence 배열 뚫어져라 보다가 큰 깨달음을 얻고 풀었다.

 

고난

for문으로 시작 인덱스를 하나하나 증가시키면서 하니까 예상했던대로 당연하게도 시간이 박살 났다. 그래서 map에 각 원소가 몇 개씩 있는지 저장해 놓고 풀려고 했는데 너무 복잡해져서 구현하다가 갈았다.