[백준, BOJ 16472] 고냥이 (java)

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

16472번: 고냥이

---

문제

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

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

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

입력

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

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

출력

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

728x90

 

예제 입력 1

2
abbcaccba

예제 출력 1

4

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 알파벳의 종류 최대 개수 N 입력
		int N = Integer.parseInt(br.readLine());
		
		// 문자열 입력
		char[] cat = br.readLine().toCharArray();
		
		int[] include = new int[26]; // 인덱스에 해당하는 문자가 몇 개 포함되어 있는지 표시하는 배열
		int count = 0; // 포함하고 있는 문자열 종류의 수
		int s = 0; // 서브문자열의 시작 인덱스
		int e = 0; // 서브문자열의 끝 인덱스
		int result = 0; // 가장 긴 서브 문자열 길이
		
		while(e < cat.length) {
			
			if(count <= N) { // 포함하고 있는 문자열 종류의 수가 N보다 작으면 문자열을 더 포함할 수 있음
				// 포함하고 있는 문자열 종류가 N보다 작거나 같을 때만 서브 문자열 길이 체크
				result = Math.max(result, e - s); // 현재 서브 문자열의 길이가 가장 큰지 체크
				
				if(include[cat[e] - 'a'] == 0) // 기존에 없던 문자열을 포함한 거라면
					count++; // 포함하고 있는 문자열 종류를 늘려줌
				include[cat[e] - 'a']++; // 인덱스에 해당하는 문자의 개수를 늘려줌
				e++;
			}
			
			else if(count > N) { // 포함하고 있는 문자열 종류의 수가 N보다 같거나 크면, 포함하고 있는 문자열을 줄여주어야 함.
				while(s < e) { // 포함하고 있던 어느 문자열의 포함 개수가 0개가 될 때까지(포함하지 않을 때까지)
					include[cat[s] - 'a']--;
					if(include[cat[s] - 'a'] == 0) {
						count--; // 포함하고 있는 문자열 개수 - 1
						s++;
						break;
					}
					s++;
				}
			}
		}
		
		if(count <= N) // 문자열의 마지막 인덱스를 포함시켰을 때 포함시킨 문자열 종류가 N을 넘지 않았다면
			result = Math.max(result, e - s); // 마지막으로 체크
		
		// 출력
		System.out.println(result);
	}
}