[백준] 16472 - 고냥이

[문제링크]

16472번: 고냥이

 

0. n글자 이내로 이루어진 가장 긴 연속된 문자열 찾기

• 투 포인터로 n글자를 유지하면서 진행한다

 

1. n+1글자가 되어 읽을 수 없을때까지 snd 포인터를 진행, 문자열을 늘린다

• 최장 문자열 길이를 갱신한다

 

2. 다시 n글자가 되어 읽을 수 있을때까지 fst 포인터를 진행, 문자열을 줄인다

 

3. snd가 끝에 도달하여 종료되었을때, 가장 길었던 문자열의 길이가 정답

 

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));
		
		int N = pint(br.readLine());
		String s = br.readLine();
		
		int maxLen=0;
		int len = 0;
		int[] cnt = new int[26];
		int kindCnt=0;
		
		int fst=0, snd=0;
		
		while(fst<=snd && snd<s.length()) {
			//1. N글자+1까지 snd 늘리면서 len 비교저장
			while(snd<s.length() && kindCnt<=N) {
				int cur = s.charAt(snd++)-'a';
				if(cnt[cur]==0)kindCnt++;
				cnt[cur]++;
				len++;
				//N+1글자일 때는 len을 갱신하면 안된다 
				if(kindCnt<=N)maxLen=Math.max(maxLen, len);
			}
			//2. N글자까지 fst 줄이기
			
			while(fst<=snd && kindCnt>N) {
				int cur = s.charAt(fst++)-'a';
				cnt[cur]--;
				if(cnt[cur]==0)kindCnt--;
				len--;
			}
			
		}
		System.out.println(maxLen);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면