[BOJ] 백준 21921. 블로그

문제

https://www.acmicpc.net/problem/21921

21921번: 블로그

 

---

풀이

 슬라이딩 윈도우 기법을 활용한 문제입니다. N의 input size가 250,000이기 때문에 for문을 두 번 돌면 제한 시간인 1초가 훨씬 넘어가게 됩니다.

 

 한 칸씩 이동하며 앞의 칸은 sum에서 빼고, 뒤의 칸은 sum에 더하는 방식으로 슬라이딩 윈도우 기법을 활용했습니다. 

 

그리고 기간이 몇 개인지도 정해야하는데, 이것은 map 자료형을 통해 key를 sum 값으로, 그리고 value는 sum에 해당하는 횟수를 더해가는 방식으로 구현했습니다.

 

아래는 소스 코드입니다.

---

소스 코드

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class B21921_블로그 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] nums = new int[N];
        int max = 0;
        for(int i =0;i<N;i++){
            nums[i] = sc.nextInt();
        }
        
        Map<Integer,Integer> map = new HashMap<>();
        int sum =0;
        for(int i=0;i<X;i++){
            sum+=nums[i];
        }
        max = sum;
        map.put(sum,map.getOrDefault(max,0)+1);
        
        for(int ed=X;ed<N;ed++){
            int st = ed-X;
            sum -= nums[st];
            sum += nums[ed];
            max = Math.max(sum,max);
            map.put(sum,map.getOrDefault(max,0)+1);
        }

        if(max==0) System.out.println("SAD");
        else {
            System.out.println(max);
            System.out.println(map.get(max));
        }
    }
}