[백준][Java] 21921번 : 블로그

[문제 링크]

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

---

문제 설명

블로그를 시작한 지 N일이 지났을 때, X일 동안 가장 많이 들어온 방문자 수와 그 기간의 개수를 구해서 출력한다.

최대 방문자 수가 0명이면 SAD 출력

 

 

 

 

 

 

문제 풀이

• 슬라이딩 윈도우 알고리즘을 활용한 문제
• 첫 번째 X일 동안의 방문자수(1일차~X일차) 합을 먼저 구한다.
• for문으로 한 칸씩 이동하면서 맨 앞의 값은 빼고 새로운 값을 더해서 구간의 합을 계산한다.

 

전체 코드

import java.io.*;
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;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   //블로그를 시작하고 지난 일수
        int x = Integer.parseInt(st.nextToken());   //최대 방문자수를 구하는 기간

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

        int visited = 0;
        //첫번째 X일 동안의 방문자 수
        for (int i = 0; i < x; i++) {
            visited += days[i];
        }

        int maxCnt = visited; //가장 많이 들어온 방문자 수
        int periodCnt = 1;  //기간의 개수
        for (int i = x; i < n; i++) {
            visited -= days[i - x];
            visited += days[i];

            if (visited > maxCnt) {
                maxCnt = visited;
                periodCnt = 1;
            } else if (visited == maxCnt) {
                periodCnt++;
            }
        }
        
        if (maxCnt == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(maxCnt + "\n" + periodCnt);
        }
    }
}

 

 

 

 

시간초과 풀이

처음에 이중 for문을 사용해서 풀었는데 시간 초과가 떴다.

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   //블로그를 시작하고 지난 일수
        int x = Integer.parseInt(st.nextToken());   //최대 방문자수를 구하는 기간

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

        int maxCnt = 0; //가장 많이 들어온 방문자 수
        int periodCnt = 0;  //기간의 개수

        for (int i = 0; i < n - x + 1; i++) {
            int visited = 0;
            for (int j = i; j < i + x; j++) {
                visited += days[j];
            }

            if (visited > maxCnt) {
                maxCnt = visited;
                periodCnt = 1;
            } else if (visited == maxCnt) {
                periodCnt++;
            }
        }

        if (maxCnt == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(maxCnt + "\n" + periodCnt);
        }
    }
}