[Java] 백준 21921 블로그

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

난이도

실버3

문제

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

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

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

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

입력

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

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

출력

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

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

내 코드

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

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[] day = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			day[i] = Integer.parseInt(st.nextToken());
		}

		int now = 0;
		for (int i = 0; i < X; i++) {
			now += day[i];
		}

		int max = now, cnt = 1;
		for (int i = X; i < N; i++) {
			now = now + day[i] - day[i - X];
			if (now > max) {
				cnt = 1;
				max = now;
			} else if (now == max) {
				cnt++;
			}

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

슬라이딩 윈도우로 푸는 문제이다.
X로 주어진 인덱스의 방문자 수 까지 합을 now에 저장하고
max에 now, cnt도 1로 초기화 해주었다.

그 다음부터는 now제일 먼저 더한 값은 빼고,
새로 들어오는 값은 더하면서 max와의 값 비교를 하면 된다.
새로운 now 값이 더 크다면 max 값 갱신과 cnt는 1로 초기화,
같다면 cnt만 1씩 더하면 된다.

슬라이딩 윈도우 문제를 오랜만에 풀어서 헷갈렸다..
앞으로 나아가면서 새로운 값은 더하고 맨 앞에 누적된 값은 빼주는 방식인걸 알았으면서
max 와 now 값을 구분하지 않고 같이 사용하는 어이없는 실수를 했다.

더 웃긴건 이런 실수를 했는데도 문제에 주어진 테스트 케이스와
질문 게시판에 있는 반례들이 통과했어서 뭐가 문제인지 찾는데 오래 걸렸다.
알고리즘은 역시 꾸준하게 푸는게 답이다...