30804 : 과일 탕후루 - JAVA

https://jinny8.tistory.com/32

투 포인터

투 포인터 문제이다.

투 포인터에 대해서는 위에서 설명했으니 생략한다.

 

처음에는 덱을 이용하여 푸는 문제인줄 알았으나, 투 포인터를 이용하여 숫자를 기록하고 1개 이상 있는것으로 기록된 숫자가 3개가 넘어가면 왼쪽 숫자를 하나 빼고, 그것을 max에 저장하고, 개중에서 최댓값만 나오도록 설정하면 된다.

 

이 역할을 하는 부분은 다음과 같다.

        while(right < n){
            cur[tanhuru[right++]]++;
            while(10 - count(cur) > 2){
                cur[tanhuru[left++]]--;
            }
            max = Math.max(max, right-left);
        }

1에서 9까지의 범위로 설정된 배열에 해당 배열의 값이 있으면 한번 더하고,

right 범위와 left 범위를 빼서, 포인터간 값을 비교를 하고,

개중 가장 크게 남은 값을 출력을 하도록 한다.

 

소스코드는 다음과 같다.

import java.util.*;
import java.io.*;
public class Main {
    static int n, m;
    static int[] tanhuru, cur;
    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;
        n = Integer.parseInt(br.readLine());
        int max = 0;
        tanhuru = new int[n];
        st = new StringTokenizer(br.readLine());
        cur = new int[10];
        for(int i = 0; i < n; i++){
            tanhuru[i] = Integer.parseInt(st.nextToken());
        }
        int left = 0;
        int right = 0;
        int index = 0;
        while(right < n){
            cur[tanhuru[right++]]++;
            while(10 - count(cur) > 2){
                cur[tanhuru[left++]]--;
            }
            max = Math.max(max, right-left);
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
    public static int count(int[] arr){
        int cnt = 0;
        for(int i : arr){
            if(i == 0){
               cnt++;
            }
        }
        return cnt;
    }
}