프로그래머스 LEVEL 2(연속된 부분 수열의 합)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-04-23

  • 해결 방법 :

    • 완전 탐색을 통해 문제 해결
      • 연속 부분 수열의 시작 인덱스와 끝 인덱스를 큐에 저장
      • 현재까지의 합에 현재 숫자를 더했을 때 k보다 작거나 같다면 끝 인덱스 증가
        • 이 때 큐에 저장된 시작 인덱스와 끝 인덱스가 현재 i와 같다면 증가 x
      • k보다 크다면 작거나 같아질 때 까지 시작 인덱스 증가
      • 현재 숫자에 대한 처리 후 sum과 k가 같다면 answer에 push

  • 회고 :

    • sequence의 길이가 1,000,000 이므로 O(n)에 문제를 해결해야 했다.

    • 따라서 처음에 연속 부분 수열의 시작 인덱스와 끝 인덱스를 큐에 저장하는 방식으로 작성했다.

      function solution(sequence, k) {
  const answer = [];
  const q = [];

  let sum = 0;

  sequence.forEach((number, i) => {
    if (sum + number < k) {
      sum += number;

      if (q.length !== 2) {
        q.push(i);
      } else {
        q[1] += 1;
      }
    } else if (sum + number > k) {
      sum += number;
      q[1] += 1;

      while (sum > k) {
        sum -= sequence[q[0]];
        q[0] += 1;
      }
    } else {
      q[1] += 1;
      answer.push([...q]);
      sum += number;

      return;
    }

    if (sum === k) {
      answer.push([...q]);

      return;
    }
  });

  return answer.sort((a, b) => (a[1] - a[0] < b[1] - b[0] ? -1 : 1))[0];
}

    • 그러나 테스트 케이스 중 4개를 통과하지 못했다..

      image

    • 곰곰이 생각해보니 [0, 0]일 때 k를 만족하는 경우에 대한 처리를 해주지 않았고, 이를 코드에 적용했더니…. 성공!!

      image

    • 그 후 코드를 더 간소화할 수 있을 것 같아 수정했다. 최종 코드는 아래와 같다!

  • 코드

    function solution(sequence, k) {
  const answer = [];
  const q = [0, 0];

  let sum = 0;

  sequence.forEach((number, i) => {
    sum += number;
    if (sum <= k) {
      if (q[1] !== i || q[0] !== i) {
        q[1] += 1;
      }
    } else if (sum > k) {
      q[1] += 1;

      while (sum > k) {
        sum -= sequence[q[0]];
        q[0] += 1;
      }
    }

    if (sum === k) {
      answer.push([...q]);
    }
  });

  return answer.sort((a, b) => (a[1] - a[0] < b[1] - b[0] ? -1 : 1))[0];
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges