백준 고냥이(16472)

고냥이

1. 힌트

1) $|S|$가 최대 $10^5$이므로 당연히 $O(N^2)$의 단순 완전 탐색으로는 불가능하다. 그리디한 해법도 떠올리기 어렵다.

2) DP로 시도하여도 부분 문제들을 잘 조합해서 만들어내기에는 문자열에 존재하는 알파벳들의 집합이 필요하다.

3) 결국 원점으로 돌아와서 효율적인 완전 탐색 방법을 찾아야 한다.

2. 접근

1) 문제를 분해할 수 있을까?

DP로 풀기 위해서 함수 $dp(i) =$ $(S[i, N)$에 포함되는 연속부분문자열 중 인식 가능한 최대 문자열의 길이$)$를 정의하여도, 부분 문제를 조합하여 문제를 풀기 위해서는 부분문제가 표현하는 구간에 어떤 알파벳이 얼마나 존재하는지를 알아야 하기 때문에 불가능하다.

9) 순서를 강제할 수 있을까?

결국 원점으로 돌아와 완전 탐색을 시도해야 한다. 좀 더 효율적인 완전 탐색은 없을까?
구간의 길이가 늘어나면 구간에 포함된 알파벳의 개수는 절대로 줄어들지 않는다는 점을 이용하면 투 포인터 알고리즘을 적용할 수 있다.
즉 구간의 시작점이 주어진다면 그 구간이 답이 될 수 있는 후보는 최대한 길이를 늘린 구간 하나뿐이라는 것이다.
후보 구간$[head, tail]$들을 앞에서부터 순회하다 보면 구간의 끝을 계속 유지하면서 순회해도 상관없다는 것을 알 수 있다.

3. 구현

public class Main {
	static String S;
	
	// S[t]를 alpha에 추가한다면 서로 다른 알파벳의 개수가 몇개가 되는지 반환
	static int getNum(int[] alpha, int num, int t) {
		return num + (alpha[S.charAt(t) - 'a'] == 0 ? 1 : 0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		S = br.readLine();
		int N = S.length();
		int head = 0; int tail = 0;
		int[] alphabet = new int[26]; alphabet[S.charAt(0) - 'a']++; int num = 1;
		int max = 1;
		// head에서 시작하는 후보 구간을 모두 검사
		while (head < N) {
			// tail을 최대한 늘린다
			while (tail + 1 < N && getNum(alphabet, num, tail + 1) <= K) {
				int t = S.charAt(++tail) - 'a';
				if (alphabet[t] == 0) num++;
				alphabet[t]++;
			}
			max = Math.max(max, tail - head + 1);
			int h = S.charAt(head++) - 'a';
			if (--alphabet[h] == 0) num--;
		}
		System.out.print(max);
	}

}

1) 시간 복잡도

while문 안의 while문은 최대 $O(|S|)$번 실행되므로 $O(|S| + |S|)$

2) 테스트 케이스