[백준_21921] 블로그

[문제]

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

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

 

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

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

 

[코드]

import java.io.*;
import java.util.*;

public class BaekJoon_21921 {

	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[] visit=new int[n];
		
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			visit[i]=Integer.parseInt(st.nextToken());
		
		int sum=0;
		int end=0;
		int max=0;
		int count=1;
		// 슬라이딩 윈도우
		for(int i=0;i<=n-x;i++) {
			// 연속 X일 동안의 방문 인원수 구하기
			while((end-i<x)&&end<n) {
				sum+=visit[end];
				end++;
			}
			
			if(max==sum)
				count++;
			else if(sum>max) {
				max=sum;
				count=1;
			}
			
			sum-=visit[i];
		}
		
		if(max==0) 
			System.out.println("SAD");
		else
		{
			System.out.println(max);
			System.out.println(count);
		}
	}

}

 

[고찰]

 이번 문제는 슬라이딩 윈도우 문제였다. 2중 for 문을 사용하면 시간초과가 나는 문제로 X일 동안의 방문객을 저장한 변수를 계속 가지고 가면서 i 번째 값을 마지막에 빼주는 식으로 구현해야 정답 처리를 받을 수 있었다.