[백준 - 16472] 고냥이 .java

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

• 최대 N개의 종류의 알파벳을 가진 연속된 문자열만 인식
• 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이 구하기
• 단, 문자열에는 알파벳 소문자만이 포함
• 번역기가 인식할 수 있는 문자열의 최대길이를 출력

 

 

getCount(int[] alp)

 

현재 창(window)에 포함된 서로 다른 알파벳의 개수를 반환

alp 배열: 각 알파벳 등장 빈도 -> 크기 26

 

 

투포인터

 

: 현재까지 포함된 알파벳 종류는 n개 이하 

-> 다음 알파벳 검사 (next)

 

next가 문자열 범위에 있을 때,

다음 알파벳을 추가하여 종류 개수 검사

n보다 크면 next가지말고 -> 한칸 뒤로, 추가했던 빈도 되돌리기 -> 더이상 증가 불가

=> i 증가 -> 현재 i 빈도 제거 후 이동

이때 정답은 최댓값 갱신

 

 

 

import java.util.*;


public class test1 {
    //현재 문자열에 속한 알파벳 종류 구하는 함수
    public static int getCount(int[] alp){
        int type =0;
        for(int i=0;i<alp.length;i++){
            if(alp[i]>0) type++;
        }
        return type;

    }
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);

        int n= sc.nextInt();
        char[] str = sc.next().toCharArray();

        int[] alpFre = new int[26];
        int next = 0, answer =0;
        for(int i =0; i<str.length;i++){
            while(next<str.length){
                //다음 알파벳 넣기
                alpFre[str[next++] -'a']++;
                //다음 알파벳 추가 안됨
                if(getCount(alpFre) > n){
                    //증가한거 취소
                    alpFre[str[--next] -'a']--;
                    break;//다음 i로 넘어가야
                }
            }
            //next는 포함안됨
            answer = Math.max(answer, next-i);
            //i빼기
            alpFre[str[i] -'a']--;
        }
        System.out.println(answer);
    }

}