[BOJ] 21921 블로그 - Java

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

21921번: 블로그

---

1. 문제

총 N일 중 X일 동안 가장 많이 들어온 방문자 수와 해당 방문자 수의 기간이 몇 개있는지 출력한다.

 

2. 풀이

슬라이딩 윈도우 문제이다.

처음에는 이중 for문으로 자리마다 X번씩 for문을 돌려주어 이미 이전에 한 번 더해진 값들이더라도 중복으로 다시 연산해서 효율이 떨어지는 문제가 있었고 제출했을 때도 시간초과가 발생했다.

슬라이딩 윈도우는 for문 한 번만으로 맨 앞값은 빼고 맨 뒷값은 더하고 이 과정을 끝까지 반복하여 효율적으로 답을 구할 수 있다.

 

3. 코드

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

/**
 * 슬라이딩 윈도우
 * 누적합 방법
 * 핵심 : 중복되는 연산을 제거
 */
public class boj_블로그 {

    static int X, N;
    static int[] arr;

    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        arr = new int[N];

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

        solution();
    }

    static void solution() {
        int max = 0;
        int sum = 0;
        int cnt = 1;
        for (int i=0; i<X; i++) {
            sum += arr[i]; //초기값
        }
        max = sum;

        for (int i=X; i<N; i++) {
            sum -= arr[i-X];
            sum += arr[i];
            if (max == sum) cnt++;
            else if (max < sum) {
                max = sum;
                cnt = 1;
            }
        }
        if (max == 0) System.out.println("SAD");
        else {
            System.out.println(max);
            System.out.println(cnt);
        }
    }

//    static void lastSolution() {
//        int max = 0;
//        int cnt = 0;
//        for (int i=0; i<N; i++) {
//            if (i+X-1 >= N) break;
//            int sum = 0;
//            for (int j=0; j<X; j++) { //이렇게 하면 안좋은 점 : 이미 계산된 값들임에도 매번 중복해서 더해야 한다. 슬라이딩 윈도우는 이런 중복되는 합 연산 과정을 제거한 방법.
//                sum += arr[i+j];
//                if (max == sum) cnt++;
//                else if (max < sum) {
//                    max = sum;
//                    cnt = 1;
//                }
//            }
//        }
//        if (max == 0) sb.append("SAD");
//        else {
//            sb.append(max).append("\n").append(cnt);
//        }
//    }
}

 

4. 사담

슬라이딩 윈도우, 누적합 문제를 싸피 초기에 한 번 풀어봤는데 이번에 다시 풀어보면서 개념을 정리할 수 있어서 좋았다.