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

블로그

문제

---

문제 설명

N 일 동안의 방문자 수가 입력으로 주어질 때 입력으로 같이 들어오는 X 일의 기간동안의 최대 방문자 수와 최대 방문자 수를 보유한 기간의 개수를 출력하는 문제이다.

---

첫번째 구현

일단 첫번째로 푼 방법은 틀렸다.

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

public class Main_21921 {
  static int n, x;
  static int[] arr;
  static int[] prefix;
  static int maxVisit = -1;
  static int maxVisitCount;
  public static void main(String[] args) throws IOException {
    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];
    prefix = new int[n];

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

    //구간 합 구하기
    for (int i = n - 1; i > 0; i--) {
      if (i - x + 1 >= 0) {
        for (int idx = i; idx > i - x; idx--) {
          prefix[i] += arr[idx];
        }
      }
      if (maxVisit < prefix[i]) {
        maxVisitCount = 1;
        maxVisit = prefix[i];
      } else if (maxVisit == prefix[i]) {
        maxVisitCount++;
      }
    }

    if (maxVisit == 0) {
      System.out.println("SAD");
    } else {
      System.out.println(maxVisit);
      System.out.println(maxVisitCount);
    }

  }
}

일단 코드부터 보면 배열에서 구간을 정해주고 해당 구간동안의 구간합을 다 구해놓고 하는 문제이다.

여기서 문제가 생기는 부분은 다음과 같다.

for (int i = n - 1; i > 0; i--) {
  if (i - x + 1 >= 0) {
    for (int idx = i; idx > i - x; idx--) {
      prefix[i] += arr[idx]; // x만큼 계속 더함 → 시간초과 위험
    }
  }

이 부분에서 계속 더해주기 때문에 잘못하면 O(n * x) 만큼의 시간복잡도가 생기고 문제에서 주어진 n 의 범위는 250,000 까지이기 때문에 시간초과가 날 수 있다.

따라서 슬라이딩 윈도우로 해당 부분을 바꿔줬다.

두번째 구현

바뀐 부분만 보자.

//처음 X일 동안의 합
for (int i = 0; i < x; i++) {
	sum += arr[i];
}

//구간 합 구하기
for (int i = x; i < n; i++) {
	sum = sum - arr[i - x] + arr[i];

	if (sum > maxVisit) {
		maxVisit = sum;
        maxVisitCount = 1;
	} else if (sum == maxVisit) {
		maxVisitCount++;
	}
}

일단 처음 시간은 X일 동안의 합을 sum 으로 두고 시작하고 아래에서 슬라이딩 윈도우를 시작한다.

앞에서 X 일동안의 합을 구해줬으니 이제 인덱스는 X 부터 n까지 간다.
그리고 기존에 구해져있던 sum에서 맨 앞 방문자수인 arr[i - x] 를 빼주고 새로 추가되는 오늘의 방문자수인 arr[i]를 더해주면 된다.

---

코드

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

public class Main_21921 {
  static int n, x;
  static int[] arr;
  static int maxVisit = -1;
  static int maxVisitCount;
  static int sum;
  public static void main(String[] args) throws IOException {
    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());
    }

    //처음 X일 동안의 합
    for (int i = 0; i < x; i++) {
      sum += arr[i];
    }
    
    maxVisit = sum;
    maxVisitCount = 1;

    //구간 합 구하기
    for (int i = x; i < n; i++) {
      sum = sum - arr[i - x] + arr[i];

      if (sum > maxVisit) {
        maxVisit = sum;
        maxVisitCount = 1;
      } else if (sum == maxVisit) {
        maxVisitCount++;
      }
    }

    if (maxVisit == 0) {
      System.out.println("SAD");
    } else {
      System.out.println(maxVisit);
      System.out.println(maxVisitCount);
    }

  }
}