[백준] 블로그 (21921) - Java

문제

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

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

 

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

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

---

입력

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

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

---

출력

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

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

---

제한

•  1 ≤ X ≤ N ≤ 250,000
•  0 ≤ 방문자 수 ≤ 8,000 

---

예제 입력 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

 

 

내가 푼 코드

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());

        long N = Long.parseLong(st.nextToken()); //블로그시작한기간
        long X = Long.parseLong(st.nextToken()); //기간
        int[] A = new int[(int)N];
        int max_view_cnt = 0;       //최대 방문자수 카운트
        int max_day_cnt = 0;        //최대 방문자수 기간 카운트
        int curr_view_cnt = 0;      //현재 방문자수 카운트

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

        // 슬라이딩윈도우 시작 index
        for (int i=0; i<N-X+1; i++) {
            if (i == 0) {
                // 초기 세팅
                for (int j=0; j<X; j++) {
                    curr_view_cnt += A[j];
                }
                max_view_cnt = curr_view_cnt;
                max_day_cnt = 1;
            } else {
                curr_view_cnt = curr_view_cnt - A[i-1] + A[(int) (i+X-1)];

                if (curr_view_cnt == max_view_cnt)
                    max_day_cnt++;
                else if (curr_view_cnt > max_view_cnt) {
                    max_view_cnt = curr_view_cnt;
                    max_day_cnt = 1;
                }
            }
        }
        String result = max_view_cnt==0 ? "SAD" : max_view_cnt + "\n" + max_day_cnt;
        System.out.println(result);
    }
}

 

슬라이딩 윈도우란 정해진 범위만큼을 기준으로 인덱스를 +1 해주어 값을 구하는 방식이다.

입력 예제1을 보면 아래와 같다.

 

여기서 시작 index는 0부터 2까지 갈수있다. (X = 5)

 

이렇게 3가지 경우가 나올 수 있다.

 

 

인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6
1	1	1	1	1	5	1

1

1

1

1

1

5

1

1

1

1

1

1

5

1

 

처음 index == 0 인 경우 초기 값을 세팅해주기 위해 if문 분기로 빼주고

나머지는 index == 0 에서 구한 방문자 수에 이전 인덱스를 (-) 해주고 이후 인덱스를 (+) 해주는 방식으로 계산하면 된다.