문제

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 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들을 길이가 짧은 순서대로 정렬해주고, 동일한 길이가 있다면 가장 먼저 나온(인덱스가 작은) 순으로 정렬해서 정답을 추려낸다.

코드

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]
}