23-07-12 TIL

문제

• 슬라이딩 윈도우
  • 백준 21921 문제를 풀고 있는데 예제는 맞았는데 시간초과가 나는 문제가 발생하였다.
  • 반복문을 중첩해서 사용한 것이 문제가 되는 거 같은데, 중첩 반복문을 사용하지 않고 푸는 방법을 시도해보아야겠다.

시도

• 슬라이딩 윈도우

  • 문제가 된 코드는 아마도 아래의 코드 같다.

  for (int i = X; i < N - X; i++) {
      for (int j = i; j < i + X; j++) sum += arr.get(j);
              int sum = 0;
              if (sum == maxSum) {
                  maxCount++;
              }
              else if (maxSum < sum) {
                  maxSum = sum;
                  maxCount = 1;
              }
  
  }

  • sum을 X의 범위 만큼 더하기 위해서 중첩된 반복문을 사용하였는데, 반복문을 1개만 가지고 풀어야 할 거 같다.
  • 그러기 위해서 sum에 arr[0], [1], [2] 를 더하고 다음 것을 더할 때에 다시 초기화를 한 후 더하는 방식을 사용하였는데 그것말고 다른 방법을 사용해보자

해결

• 슬라이딩 윈도우
  • arr 1, 2, 3을 더하고 다음에는 2, 3, 4를 더하기 이것은 기존에 있던 1번째 인덱스 값을 제거하고 4번째 인덱스 값을 더하는 것과 같다.
  • 따라서 sum 중첩합을 구할 경우에 sum = arr[i] - arr[i - X]를 한다면 굳이 중첩된 반복문을 사용하지 않아도 될 것으로 보인다.
    -> 이 방법을 슬라이딩 윈도우라고 한다고 함....

	for (int i = X; i < N; i++) {
            sum += arr.get(i) - arr.get(i - X);

            if (sum == maxSum) {
                maxCount++;
            }
            else if (maxSum < sum) {
                maxSum = sum;
                maxCount = 1;
            }
    }

오늘 푼 문제

• 백준 21921 (블로그) - Java
  • 반복문 두개를 사용해서 풀면 시간 초과가 나는 문제이다.
  • 반복문을 중첩하지 말고 미리 sum을 더해놓고 하나 빼고 하나 더하는 식으로 풀면 시간내에 풀 수 있다.

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 지방의 수
        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");

        ArrayList<Integer> arr = new ArrayList<>();

        for (int i = 0; i < N; i++) arr.add(Integer.parseInt(st.nextToken()));

        int sum = 0;
        int maxCount = 1;

        for (int i = 0; i < X; i++) sum += arr.get(i);

        int maxSum = sum;
        for (int i = X; i < N; i++) {
            sum += arr.get(i) - arr.get(i - X);

            if (sum == maxSum) {
                maxCount++;
            }
            else if (maxSum < sum) {
                maxSum = sum;
                maxCount = 1;
            }
        }

        if (maxSum == 0)    bw.write("SAD\n");
        else bw.write(maxSum + "\n" + maxCount);

        bw.flush();
        bw.close();
        br.close();
    }
}