[백준] 30804. 과일 탕후루(슬라이딩 윈도우) - JAVA

문제

 

---

 

풀이

 

해당 문제를 풀기 위해서는 우선, 슬라이딩 윈도우를 알아야 한다.

슬라이딩 윈도우란? 배열이나 문자열처럼 연속된 데이터를 다룰 때, 일정 크기의 구간(윈도우)를

설정하고 그 구간을 한 칸씩 밀면서 문제를 푸는 방식이다.

보통 구간 합, 최대/최소값, 특정 패턴 탐색 같은 문제에서 많이 사용하며,

매번 새로 합이나 조건을 계산하지 않고, 앞에서 빠지는 값은 빼고 새로 들어오는 값만 더해서 효율적으로 계산한다.

 

예시를 들어보자면 배열 arr[N] 이 있다고 가정해보자, 

이때 구간 3개중 최대 값을 구하려고 한다.

 

가장 좌측 부터 3개를 더한다. 

즉, arr[0]+arr[1]+arr[2]를 사용할 것이다.

 

 

다음은 한칸씩 밀리는데 이때

중복되는 구간이 arr[1]+arr[2] 부분이다.

이 계산을 중복방지하기 위해서 arr[0]을 빼고, arr[3]을 더해주는 방법이다.

이러한 방법을 통해 최대값 혹은 최소값을 배열에서 찾아낼 수 있다.

 

이제 문제를 보면,

배열에 양쪽 끝에서 삭제가 이루어지는 과정에서 2개의 과일 종류만

남겼을 때 길이의 최대값을 찾는 문제이다.

 

문제를 해결하기 위해 슬라이딩 윈도우를 응용할 것이고,

과일의 종류를 카운트하기 위해 HashMap을 사용한다.

 

1. HashMap.put(arr[right] , HashMap.getOrDefault(arr[right],0)+1) 으로 과일을 카운트를 해준다.

2. 만약 HashMap의 사이즈가 2를 초과할 경우 HashMap.get(arr[left]) 이 0이 될때까지 left를 우측으로 이동 시킨 후

3. HashMap.remove(arr[left]) 을 통해 다시 과일의 종류가 2개를 유지시켜준다.

 

이렇게 right가 배열에 사이즈만큼 반복하다보면 과일의 종류가 2개일 때 최대 길이을 찾아낼 수 있다.

 

---

코드

 

import java.io.*;

import java.util.*;

 

public class Main{

    public static void main(String[] args)throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        int max = 0;

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

        for(int i=0; i<N; i++){

            arr[i] = Integer.parseInt(st.nextToken());

        }

        HashMap<Integer,Integer> map = new HashMap<>();

        int left = 0;

        for(int right=0; right<N; right++){

            map.put(arr[right], map.getOrDefault(arr[right],0) + 1 );

            while(map.size()>2){

                map.put(arr[left], map.get(arr[left])-1);

                if(map.get(arr[left])==0){

                    map.remove(arr[left]);

                }

                left++;

            }

            max = Math.max(max, right-left+1);

        }

        System.out.print(max);

    }

}