[자바] 백준 21921 - 블로그 (java)

목차

문제 : boj21921

 

 

필요 알고리즘

• 슬라이딩 윈도우 또는 누적합
  
  • 둘 중 하나로 풀면 쉽게 풀 수 있다. 다른 방법들도 많을 것 같다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  내 경우엔 슬라이딩 윈도우로 풀었다. 그림으로 보면 쉽게 이해될 것 같다.

5 3
1 4 2 5 1

위의 예시의 경우 그림으로 풀이를 그려보면 다음과 같다.

 

 

  저 X칸짜리 주황색 부분을 옆으로 그대로 움직이듯이 움직이므로 '슬라이딩 윈도우' 라고 부른다. 처음 이미지에서 합은 7이었고, 옆으로 한칸 밀 땐 새로 들어온 '5'를 더하고, 빠지는 '1'을 빼주면 된다. 즉, 7+5-1 = 11 이다. 이런식으로 주황색 부분의 합 중 가장 큰 값이 답이 된다.

 

  그리고 최대 방문자였던 기간이 몇 개 있는지는 다음과 같이 처리해주면 된다.

if (max == sum) maxCnt++;	// 현재 최대치와 동일하면 카운팅해준다.
else if (max < sum) {	// 현재 최대치보다 크다면
    max = sum;	// max값을 변경해주고
    maxCnt = 1;	// 카운팅하던걸 갱신해준다.
}

 

 

코드 : github

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

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

        int sum = 0;
        for (int i = 0; i < x; i++) sum += arr[i];

        int max = sum;
        int maxCnt = 1;
        for (int i = x; i < n; i++) {
            sum += arr[i] - arr[i-x];
            if (max == sum) maxCnt++;
            else if (max < sum) {
                max = sum;
                maxCnt = 1;
            }
        }
        if (max == 0) {
            System.out.println("SAD");
            return;
        }
        System.out.println(max);
        System.out.println(maxCnt);
    }
}