[16472] 고양이

🔗 문제 링크

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

🔍 문제 설명

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

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

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

⚠️ 제한사항

• $(1 < N ≤ 26), (1 ≤ 문자열의 길이 ≤ 100,000)$

• 단, 문자열에는 알파벳 소문자만이 포함된다.

---

🗝 풀이 (언어 : Java)

투포인터 문제로 오른쪽 인덱스는 다시 돌아오지 않고 계속 뒤로만 가기때문에 시간복잡도는 $O(N)$이다.
왼쪽 포인터를 기준으로, 오른쪽 포인터를 뒤로 1씩 이동시킨다. 종류가 N보다 커지면 왼쪽 포인터를 뒤로 1만큼 이동시킨다. 해당 순서의 알파벳의 개수와 종류수를 그때그때 파악하기 위해 정수 배열을 선언하여 활용한다.다음 알파벳으로 종류가 N보다 커져도 오른쪽 포인터를 이동시키고 바로 다음 순서에 왼쪽 포인터를 이동시킨다.
종류가 N이하일 경우에만 문자열 길이의 최대값을 갱신해준다.

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

class Main {
    private static int findMaxLength(int n, char[] chars) {
        // 최대 길이, 왼쪽 & 오른쪽 인덱스, 알파벳 종류 수
        int answer = 0, left = 0, right = 0, count = 0;
        int[] alpha = new int['z'-'a'+1]; // 알파벳별 개수
        while (left <= right && right < chars.length) {
            char c;
            if (count <= n) { // N이하의 알파벳 종류면 right+1
                c = chars[right];
                if (alpha[c - 'a'] == 0) // 새로운 알파벳이면 카운트+1
                    count++;
                alpha[c - 'a']++; // 해당 알파벳 개수+1
                right++;
            } else { // N이상의 알파벳 종류면 left+1
                c = chars[left];
                alpha[c - 'a']--; // 해당 알파벳 개수-1
                if (alpha[c - 'a'] == 0) // 왼쪽 알파벳 종류 더이상 없으면 카운트-1
                    count--;
                left++;
            }
            if (count <= n) // N이하의 종류 길이 경우만 최대값 갱신
                answer = Math.max(answer, right - left);
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] chars = br.readLine().toCharArray();
        br.close();
        System.out.println(findMaxLength(n, chars));
    }
}