[JAVA] 백준 16472 고냥이_큐

 

문제 : 

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

 

 

접근 : 

 

 - 들어온 수를 큐와 set, count 배열에 넣는다.

 

 - 만약 set 이 n 보다 클 경우 큐에서 1개씩 제거하면서 count의 수를 줄이고 count 수가 0 이되면 set에서 제거한다.

 

 - 제거 후 큐의 길이를 기존 값과 비교하면서 더 큰 값으로 갱신 후 출력한다.

 

 

코드구현 : 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());

        String inputs = br.readLine();

        Queue<Character> q = new LinkedList<>();
        Set<Character> in_storage = new HashSet<>();
        int[] storage = new int['z' - 'a' + 1];

        int ans = 0;
        char now;
        char removed;

        for(int j = 0 ; j < inputs.length(); j++){
            now = inputs.charAt(j);
            q.offer(now);
            in_storage.add(now);
            storage[now - 'a']++;

            while(in_storage.size() > n){
                removed = q.poll();
                if(--storage[removed - 'a'] == 0) in_storage.remove(removed);
            }

            ans = Math.max(ans, q.size());
        }

        System.out.println(ans);
        br.close();
    }
}