[Baekjoon] 백준 21921 블로그 (S3 / 누적합) - Java

링크

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

21921번: 블로그

 

 

 

 

문제 해석

N일 중 X일 동안 가장 많이 들어온 방문자수,
방문자가 최대인 기간이 몇 개 있는지 구하기

 

 

- 입력
첫 번째 줄 : N X
  N : 블로그를 시작하고 지난 일수
  X : 구하고자 하는 기간
두 번째 줄 : 1일부터 N일까지 하루 방문자 수


- 출력
if 최대 방문자 수가 0이라면: 
SAD

else:
X일 동안 가장 많이 방문한 방문자 수
최대 방문자수인 기간 개수

 

 

 

 

풀이 & 코드 해석

누적합을 사용하면 쉽게 풀 수 있는 문제입니다.

 

누적합을 저장하는 배열 s[]를 생성한 후, 슬라이딩 윈도우를 통하여 기간 내 최대 값을 탐색하면서 결과를 얻어냅니다.

 

 

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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 a[] = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int s[] = new int[N + 1];
        s[0] = 0;
        s[1]= a[0];

        for (int i = 2; i < s.length; i++) {
            s[i] = s[i - 1] + a[i - 1];
        }

        int max = 0;
        int maxCount = 0;

        for (int i = X; i < s.length; i++) {
            int now = s[i] - s[i - X];

            if (now == max) {
                maxCount++;
            }

            if (now > max) {
                max = now;
                maxCount = 1;
            }
        }

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

    }
}

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java