문제

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 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 배열의 길이가 1,000,000이라는 점이다. 따라서, 절대 이중 for loop을 사용해서는 풀 수 없겠다고 생각했고, O(N) 으로 코드를 설계해야겠다고 생각했다.
  • 혹시 몰라서 그냥 O(N^2)으로 이중 for loop 돌려봤는데 역시나 시간초과 파티 (최소 사이즈의 부분 수열을 구하라고 해서 sequence 배열을 뒤에서부터 탐색하면서, end를 고정해놓고 start를 앞으로 옮겨가면서 그때마다의 부분합을 계산하고, 부분합이 크다면 end--시켜서 start의 위치도 다시 end와 일치시키고 처음 과정을 반복했다.)
• O(N)으로 설계하기 위해 투 포인터 알고리즘을 이용하였다.
  0. 정답이 될 수 있는 후보들의 배열을 candidate로 선언한다.
  1. 부분수열의 시작과 끝을 s, e라는 포인터로 지정한다. 부분합(sum)은 sequence[s]로 초기화한다.
     • sum > k => sum에서 sequence[s]를 빼고, s를 증가시킨다.
     • sum < k => e를 증가시키고, sum에 sequence[e]를 더한다.
     • sum == k => candidate 배열에 현재 [s, e] 배열을 추가하고, s와 e를 각각 1씩 증가시킨다.
  2. 이 모든 과정을 e < sequence.length일 동안 반복한다.
  3. 마지막으로 candidate들을 길이가 짧은 순서대로 정렬해주고, 동일한 길이가 있다면 가장 먼저 나온(인덱스가 작은) 순으로 정렬해서 정답을 추려낸다.

풀이 요약

sol. 
누적 합 행렬을 사용하여 구간합을 빠르게 계산할 수 있도록 한다.
수열은 오름차순으로 정렬되어 있고, 연속된 수열의 합을 계산하기 때문에 
두 개의 포인터를 사용하여 목표 값 k 를 찾도록 한다

앞쪽 포인터는 그대로 두고 뒤쪽 포인터를 이동시켜가며 k 값에 가까워지는지 확인한다
만약 구간 합이 k 보다 작다면 더 큰 수가 필요한 것 이기 때문에 뒤쪽 포인터를 더 뒤로 이동시킨다
만약 구간 합이 k 보다 크다면 구간 내에서 일정 값을 덜어내야 하기 때문에 작은 값들을 먼저 버리도록 앞쪽 포인터를 뒤로 이동시킨다

만약 구간 합이 k 인 지점을 찾았다면 정답을 기록한다. 
이 때 구간합에 사용된 요소 개수가 작은 구간을 선택하도록 한다.

코드

Javascript 코드

function solution(sequence, k) {
    var candidate = [];
    
    // s는 시작인덱스, e는 끝인덱스
    let s = 0, 
        e = 0;
    let sum = sequence[0];
    
    while(e < sequence.length) {
        if(sum < k) sum += sequence[++e];
        if(sum > k) sum -= sequence[s++];
        if(sum == k) {
            candidate.push([s, e]);
            sum += sequence[++e];
            sum -= sequence[s++];
        }
    }
    
    // candidate를 부분수열의 사이즈가 작은 순서대로 정렬
    candidate.sort((next, prev) => (next[1] - next[0]) - (prev[1] - prev[0]));
    const filtered = candidate.filter(c => c[1] - c[0] === candidate[0][1] - candidate[0][0]).sort((next, prev) => next[0] - prev[0])
    
    return filtered[0]
}

Python 코드
Python으로는 조금 다른 접근 방식으로 풀었는데, 그 풀이는 다음과 같다.

1. 구간합(Prefix sum) 방식으로 처음부터 끝까지의 구간합을 저장한다.
   예를 들어, [1, 2, 3, 4, 5] 배열이면 구간합은 [0, 1, 3, 6, 10, 15]가 되겠다.
2. 구간합 배열의 인덱스를 역으로 defaultdict로 기록한다.
   예를 들어, {0: 0, 1: 1, 3: 2, 6: 3, 10: 4, 15: 5}가 되겠다.
3. 구간합 배열을 순회하면서 목표치인 K보다 클 때 다음과 같이 검사한다:
   • 현재 구간합 원소에서 K에 도달하기 위해 need만큼 빼야 한다고 하자.
   • defaultdict에 need를 키로 가지고 있는 부분이 있는지 체크하고, 만약 있다면[defaultdict[need], 현재구간합 순회인덱스-1]의 길이와 기존 정답의 길이와 비교해서 더 작은 값이면 정답으로 저장한다.
   • defaultdict에 need를 키로 가지고 있는 부분이 없다면, defaultdict[need]가 새로 생성되었으므로 반복문이 제대로 돌기 위해서 삭제 해주어야 한다. (del)

from collections import defaultdict

def solution(sequence, k):
    #prefix_sum: 구간합을 기록하는 배열
    #sum_map: 구간합이 나온 sequence의 인덱스를 기록하는 딕셔너리
    prefix_sum = [0]
    sum_map = defaultdict(int)
    sum_map[0] = 0
    index = 1
    for n in sequence:
        cursum = prefix_sum[-1] + n
        prefix_sum.append(cursum)
        sum_map[cursum] = index
        index += 1
    
    #구간합 배열을 순회하면서 모자란 값을 찾으면 answer를 업데이트
    answer = [0, 0]
    minlen = 9999999
    for idx, n in enumerate(prefix_sum):
        if n >= k:
            #need: 빼야하는 값
            need = n - k
            if need != 0 and sum_map[need] == 0:
                del(sum_map[need])
                pass
            else:
                comp = idx - sum_map[need]
                if minlen > comp:
                    minlen = comp
                    answer = [sum_map[need], idx-1]
    
    return answer