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

📝 [Lv2] 연속된 부분 수열의 합

👀 문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

🚨 제한 사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
  • 1 ≤ sequence의 원소 ≤ 1,000
  • sequence는 비내림차순으로 정렬되어 있습니다.
• 5 ≤ k ≤ 1,000,000,000
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

 

💻 입출력 예

sequence	k	resulst
[1, 2, 3, 4, 5]	7	[2, 3]
[1, 1, 1, 2, 3, 4, 5]	5	[6, 6]
[2, 2, 2, 2, 2]	6	[0, 2]

 

✨ 풀이 설명

문제를 보니 투포인터 방법이 생각났다. 두 개의 포인터로 배열의 인덱스를 접근하며 시간 복잡도를 줄일 수 있는 방법이다. 시작 지점에서 시작한 두 점 left, right를 두고, right는 계속 순차적으로 나아간다. left는 조건에 따라 right를 따라갈 수 있다.

나는 right번째의 값을 sum에 계속 더하며 k가 되는지 확인해 주었다. 만약 sum이 k를 넘어가게 되면, left를 인덱스로 갖는 값을 빼주면서 right를 쫓아갔다.
만약 k가 4이고 sequence가 [1, 2, 3, 4] 라면, right가 2가 되었을 때 sum은 6으로 k보다 커지게 되어 앞에서부터 하나씩 빼주게 된다. left가 0인 1을 빼준 후, 값을 비교하였을 때, 아직도 k보다 크므로 left가 1인 2를 빼주었다.
후위 증가연산자를 사용해준 이유는, 0부터 검사한 후, left를 이동시켜야 하기 때문이다.

이렇게 반복하다 sum이 k가 되고, 이전 저장된 인덱스의 차(=== 배열의 길이) 보다 작아지게 될 때, left와 right의 값을 재할당했다.

reduce()로 두 인덱스를 반환하고자 하였고, k는 항상 sequence의 부분 수열로 만들 수 있는 값이기 때문에 제한 사항에서 가능한 가장 작은 값부터 큰 값을 저장하였다. (중간에 무조건 재할당이 이루어질 수 있도록)

 

🕵️‍♂️ 코드

function solution(sequence, k) {

  let left = 0, sum = 0;

  return sequence.reduce(([start, end], num, right) => {

    sum += num;

    while (sum > k) sum -= sequence[left++];

    if (sum === k && end - start > right - left) return [left, right];

    return [start, end];

  }, [0, 10e5]);

}