[백준] 21921: 블로그 (JAVA)

문제

찬솔이는 블로그를 시작한 지 벌써 N$N$일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

예제 입력 1 복사

5 2
1 4 2 5 1

예제 출력 1 복사

7
1

예제 입력 2 복사

7 5
1 1 1 1 1 5 1

예제 출력 2 복사

9
2

예제 입력 3 복사

5 3
0 0 0 0 0

예제 출력 3 복사

SAD

 

풀이

최근에 투포인터에 이어 슬라이딩 윈도우 알고리즘을 알게 되었는데, 이 문제도 그대로 슬라이딩 윈도우 알고리즘을 적용하면 되는 문제였다. 대신 기간의 개수를 출력해줘야 하므로 Math.max 대신 if문으로 처리해주었다.

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(slidingWindow(arr, x));
    }

    static StringBuilder slidingWindow(int[] arr, int x) {
        int max = 0;
        int sum = 0;
        int cnt = 1;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < x; i++) {
            sum += arr[i];
        }
        max = sum;

        for (int i = x; i < arr.length; i++) {
            sum += arr[i] - arr[i - x];
            if (sum > max) {
                max = sum;
                cnt = 1;
            } else if (sum == max) {
                cnt++;
            }
        }

        if (max == 0) sb.append("SAD");
        else sb.append(max).append("\n").append(cnt);

        return sb;
    }
}