[백준] 10025 게으른 백곰 - 슬라이딩 윈도우(Sliding Window) JAVA

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

코드설명

슬라이딩 윈도우(Sliding Window) 를 활용합니다.

 

문제에서 가장 헷갈린 점은, Sliding Window에서 주어진 K를 (K*2 +1)로 처리한뒤 이것을 일종의 간격이라고 생각하는 것 입니다.

for(int i=(K * 2 + 1) - 1; i<=1000000; i++) {
    slidingSum += ice[i];
    answer = Math.max(answer, slidingSum);
    slidingSum -= ice[i - (K * 2 + 1) + 1];
}

i - (K*2+1) +1 을 통해서 i번쨰 위치에서  - (K*2+1) + 1 만큼의 앞쪽으로 이동하여 빼주고, 하는 과정을 유의합니다.

 

만약 K가 500000이라면, 모든 양동이들의 위치보다 더 커집니다. 그러므로 ArrayIndexOutOfRange가 발생할 수 있는데, 이 경우에는 최대값이므로 모든 양동이를 다 움직여서 가져갈 수 있으므로 다 더해서 반환합니다.

//만약 K가 500000이라면, 모든 양동이를 다 움직여서 가져갈 수 있으므로 다 더해서 반환한다.
if( (K * 2 + 1) >= 1000000) {
    for(int i=0; i<=1000000; i++) {
        answer += ice[i];
    }
    System.out.println(answer);
    return ;
}

 

혹은, 아래와 같이 더 깔금하게 처리할 수 있습니다.

for(int i=0; i< (K * 2 + 1) - 1 && i<= 1000000; i++) {
    slidingSum += ice[i];
}
answer = Math.max(answer,  slidingSum);

코드

정답코드 1입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    private static int N, K;
    private static int answer = 0;
    private static int slidingSum = 0;
    private static int[] ice;
    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());
		K = Integer.parseInt(st.nextToken());
		
		ice = new int[1000001];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int g = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			ice[x] += g;
		}
		
		//만약 K가 500000이라면, 모든 양동이를 다 움직여서 가져갈 수 있으므로 다 더해서 반환한다.
		if( (K * 2 + 1) >= 1000000) {
			for(int i=0; i<=1000000; i++) {
				answer += ice[i];
			}
			System.out.println(answer);
			return ;
		}
		
		for(int i=0; i< (K * 2 + 1) - 1; i++) {
			slidingSum += ice[i];
		}
		
		for(int i=(K * 2 + 1) - 1; i<=1000000; i++) {
			slidingSum += ice[i];
			answer = Math.max(answer, slidingSum);
			slidingSum -= ice[i - (K * 2 + 1) + 1];
		}
		System.out.println(answer);
	}
    
}

 

K가 범위를 벗어날경우를 반복문 조건문에 조건을 넣어서 처리 그리고 answer 갱신.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    private static int N, K;
    private static int answer = 0;
    private static int slidingSum = 0;
    private static int[] ice;
    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());
		K = Integer.parseInt(st.nextToken());
		
		ice = new int[1000001];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int g = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			ice[x] += g;
		}
		
		//만약 K가 500000이라면, 모든 양동이를 다 움직여서 가져갈 수 있으므로 다 더해서 반환한다.
//		if( (K * 2 + 1) >= 1000000) {
//			for(int i=0; i<=1000000; i++) {
//				answer += ice[i];
//			}
//			System.out.println(answer);
//			return ;
//		}
		
		for(int i=0; i< (K * 2 + 1) - 1 && i<= 1000000; i++) {
			slidingSum += ice[i];
		}
		answer = Math.max(answer,  slidingSum);
		
		for(int i=(K * 2 + 1) - 1; i<=1000000; i++) {
			slidingSum += ice[i];
			answer = Math.max(answer, slidingSum);
			slidingSum -= ice[i - (K * 2 + 1) + 1];
		}
		
		System.out.println(answer);
	}
    
}