Baekjoon 16472 고냥이 JAVA

16472번: 고냥이

문제

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)

둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다. 

풀이

1. 두 포인터를 이용하여 문자열을 범위구간으로 나눠가며 답을 찾는다.

2. 최대로 가질 수 있는 문자의 개수를 N개이기에 이용하는 범위안에서 서로 다른 문자의 개수가 N개미만이면 새로운 문자를 추가

3. 현재 있는 문자가 몇개인지 판단하기 위해서 사용하는 알파벳의 개수를 저장하면서 0에서 1이 되는 순간 사용 알파벳의 값을 증가, 1에서 0이 되는 순간 사용 알파벳의 개수를 감소

4. 현재 범위에 있는 문자의 개수가 N보다 크면 이 범위의 문자는 최대 길이가 될 수 없기에, 앞에 포인터를 뒤로 당기면서 사용하는 문자의 개수를 감소

5. 현재 사용하는 알파벳의 개수가 N보다 작으면 최대 길이를 갱신한다.

코드

import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(),m=0, ans=0, s=0, e=0;
		String str = sc.next();
		int [] alpha = new int [26];
		while(s<=e && s<str.length()) {	// 투포인터를 이용, 시작점이 str의 길이를 넘지 않도록 함
			int cur;	// 현재 쓰는 문자
			if(m<=n && e<=str.length()-1) {	// 뒷부분이 늘어나는 경우, 갯수가 넘으면서 e가 최대 길이보다 짧을 때
				cur = str.charAt(e++)-'a';
				alpha[cur]++;	// 사용하는 문자의 갯수를 추가
				if(alpha[cur]==1)	// 만약 사용하는 문자의 개수가 1이라면 방금 추가된게 처음이므로
					m++;			// 사용중인 알파뱃의 종류를 추가
			}
			else {
				cur = str.charAt(s++)-'a';
				alpha[cur]--;		// 사용하는 알파벳의 개수를 감소
				if(alpha[cur]==0)	// 0개 사용중이면 사용하지 않기에 사용하는 알파뱃의 종류를 감소
					m--;
			}			
			if(m<=n && e-s>ans)	// 사용하는 알파뱃의 개수가 n보다 작을때 최대길이를 업데이트
				ans=e-s;				
		}
		System.out.println(ans);
	}
}