[Java, 자바] 백준 21921번, 블로그

백준 21921번

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

난이도 : 실버3

---

문제내용

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

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

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

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

---

입력

 

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

---

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

<제한>

•  1 ≤ X ≤ N ≤ 250,000
•  0 ≤ 방문자 수 ≤ 8,000

---

풀이방법

문제 내용에서 이해가 어려웠던 부분은 기간이 몇 개 있는지를 구라하는 구분이 '이게 뭐지 ?' 싶었는데 제일 큰 누적의 합이 몇번 나오는지를 구하면 되는거였다 !

이번 문제는 반복문을 중첩해서 해결할 경우 분명 시간 초과가 발생할 것이라고 생각했다.

중첩 반복문을 사용할 경우 O(n^2)의 시간 복잡도가 발생하지만 '슬라이딩 윈도우'와 '투포인터' 알고리즘을 통해 O(n)으로 줄일 수 있다.

슬라이딩 윈도우의 내용은 알고리즘 카테고리에서 확인할 수 있습니다 :)

반목문을 이용하여 sum의 변수에 구하고 싶은 1일차부터 x일차만큼의 값을 누적하였다.

answer의 1번째 배열을 1로 초기화줘야 되는거 빼먹지 말기 !

그 이후 lt의 값은 0으로 설정하고 rt의 값은 x일로 설정해 놓았다.

누적의 합 변수 sum에 arr[rt]를 더해주고 arr[lt]를 빼주었다 ! 

그리고 큰수를 answer의 0번째 배열에 넣어주었다. 기간을 구하는 내용이 없을 때 Math.max()를 활용하면 코드가 깔끔해진다 !

그리고 값이 동일할 때 answer의 1번째 배열을 증가시켜주었다.

여기서 중요한 건 answer의 0번째 배열의 값이 바뀔 때 answer의 1번째 배열을 1로 초기화해주어야된다는 점 ! 

---

코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int day = scan.nextInt();
        int x = scan.nextInt();
        int[] arr = new int[day];
        int[] answer = new int[2];
        int sum = 0, lt = 0;
        for (int i = 0; i < day; i++) arr[i] = scan.nextInt();
        for (int i = 0; i < x; i++) {
            sum += arr[i];
            answer[0] += arr[i];
            answer[1] = 1;
        }
        for (int rt = x; rt < day; rt++) {
            sum += arr[rt];
            sum -= arr[lt++];
            if (answer[0] == sum) answer[1]++;
            else if (answer[0] < sum) {
                answer[0] = sum;
                answer[1] = 1;
            }
        }
        if (answer[0] == 0) System.out.println("SAD");
        else {
            for (int x : answer) System.out.println(x);
        }
    }
}