[자바/누적합] 코드트리. 연속한 K개의 숫자

문제

문제 링크

해석

해당 문제는 기본 구현으로도 가능하고, 누적합으로도 가능하다. 한번 살펴보자.

• 기본 구현
  제외되는 숫자들이 B 개만큼 존재한다고 하면, 그 숫자들을 Hash Set을 이용하여 관리하고, 1부터 n까지 슬라이딩 윈도우 느낌으로 k의 길이만큼 연속된 수열을 한칸 한칸 밀면서 매 이동마다 다음에 추가되는 숫자가 B개의 숫자 중 하나이면 cnt++, 그리고 이동마다 다음에 빠지는 숫자가 B개의 숫자 중 하나이면 cnt--로 연산한다. 이렇게 계산하면서 매 이동마다 cnt의 최소값이 뭔지만 갱신해주면 답을 찾을 수 있다.
• 누적합
  하지만 잘 생각해보면 이 방식은 매번 이동마다 수행해야 하는 연산량이 (상대적으로) 많다. 하지만 이를 미리 계산해둘 수 있다면 어떨까? 각 구간별로 누적 cnt 값이 몇인지 계산해두면 더욱 시간이 단축될 것이다. 이처럼 누적합은 단순 구현 방식의 문제 중에서 실행 시간을 효과적으로 단축할 수 있는 스킬 중 하나로 활용된다.

로직

두 가지 방식을 메서드화하여 구분해 두었으니 이를 참고해서 확인하면 된다.

package 알고리즘연습.codetree;  

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.HashSet;  
import java.util.Set;  
import java.util.StringTokenizer;  
import java.util.stream.IntStream;  
import java.util.stream.Stream;  

public class CodeTree_연속한K개의숫자 {  
    private static BufferedReader br;  
    public static void main(String[] args) throws IOException {  
        br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int n = Integer.parseInt(st.nextToken()); // 숫자 범위  
        int k = Integer.parseInt(st.nextToken()); // k개의 연속  
        int b = Integer.parseInt(st.nextToken()); // 없는 숫자 개수 b       
        // int ans = getAnswerByBasicImplementation(b, k, n);  
        int ans = getAnswerByPrefixSum(n, k, b);  // 더 빠른 방식
        System.out.println(ans);  
    }  

    /**
    * 일반 구현 방식
    */
    private static int getAnswerByBasicImplementation(int b, int k, int n) throws IOException {  
        // time complexity : O(N)  
        // 실행 시간 : 372ms        Set<Integer> s = new HashSet<>();  
        for (int i = 0; i < b; i++) {  
            s.add(Integer.parseInt(br.readLine()));  
        }  

        int cnt = (int) IntStream.rangeClosed(1, k).filter(s::contains).count(); // 없는 숫자 카운트  

        int[] ps = new int[n + 1];  
        int[] arr = new int[n + 1];  
        for (int i = 1; i <= n; i++) {  
            ps[i] = ps[i - 1] + i;  
            arr[i] = s.contains(i) ? 0 : i;  
        }  
        int ans = cnt;  
        // 1부터 n까지  
        for (int i = k + 1; i <= n; i++) {  
            if (i != arr[i]) {  
                cnt++;  
            }  
            if ((i - k) != arr[i - k]) {  
                cnt--;  
            }  
            ans = Math.min(ans, cnt);  
        }  
        return ans;  
    }  

      /**
    * 누적합 활용 방식
    */
    private static int getAnswerByPrefixSum(int n, int k, int b) throws IOException{  
        // time complexity : O(N)  
        // 실행 시간 : 125ms        int[] arr = new int[n + 1];  
        for (int i = 0; i < b; i++) {  
            int idx = Integer.parseInt(br.readLine());  
            arr[idx] = 1; // 해당하지 않는 인덱스는 0으로 초기화됨  
        }  
        int[] prefixSum = new int[n + 1];  
        for (int i = 1; i <= n; i++) {  
            prefixSum[i] = prefixSum[i - 1] + arr[i];  
        }  
        int ans = Integer.MAX_VALUE;  

        for (int i = k; i <= n; i++) {  
            ans = Math.min(ans, prefixSum[i] - prefixSum[i - k]);  
        }  
        return ans;  
    }  

}