[백준] 16472: 고냥이 - JAVA

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

 

풀이

문자열을 최대 N개 종류의 알파벳을 가진 문자열로 잘라야한다.

 

abbcaccba 라는 문자열을 최대 2개 종류의 알파벳을 가진 문자열로 자르면 cacc 일때 길이가 4로 최대가 된다.

 

알파벳의 개수를 int 배열을 통해 저장하고, 새로운 알파벳이 나올 때마다 cnt를 늘려가면서 탐색한다.

 

이때 탐색은 투포인터 알고리즘으로 한다. cnt가 n보다 크면 left를 1늘려서 문자열의 길이를 줄이고,

 

cnt가 n보다 작거나 같다면 right를 1늘려서 문자열의 길이를 늘린다.

 

---

 

메모리: 15492KB
시간: 160ms
언어: Java 11

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String input = br.readLine();

        int[] alphabet = new int[26];

        int left = 0;
        int right = 0;
        int cnt = 0;
        int answer = 0;

        alphabet[input.charAt(0) - 97]++;
        cnt++;
        while (right < input.length() - 1) {

            if (cnt <= n) {
                right++;
                if (alphabet[input.charAt(right) - 97] == 0) {
                    cnt++;
                }
                alphabet[input.charAt(right) - 97]++;
            } else {
                alphabet[input.charAt(left) - 97]--;
                if (alphabet[input.charAt(left) - 97] == 0) {
                    cnt--;
                }
                left++;
            }

            if (cnt <= n) {
                answer = Math.max(answer, right - left + 1);
            }
        }

        System.out.println(answer);
    }
}