[백준] 16472 - 고냥이 (java)

Baekjoon 16472 - 고냥이 (클릭 시 이동)

문제

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

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	1394	600	451	42.871%

입력

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

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

출력

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

풀이

count : 알파벳 종류의 갯수

1. 알파벳을 카운트할 26칸짜리 배열을 선언한다.
2. 0번 인덱스에서 투포인터로 출발한다.
3. end를 1칸 늘리고 해당 칸의 알파벳이 처음 나온 것이면 (alphabet[ (end) ] == 0) count를 증가시킨다.
4. 만약 count 가 N보다 크면 start를 1칸 늘리면서 alphabet 배열의 값을 줄인다.
5. 배열의 값 중 하나가 0이 되면 count를 감소시킨다. 이 때 까지 4를 반복한다.
6. Answer의 값을 갱신한다 ( Ans = Math.max(Ans, end - start + 1) )

최종 소스코드

import java.io.*;

public class BJ_G4_16472_고냥이 {
    static int N, Ans = 0;
    static int[] alphabet = new int[26];
    static String str = null;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        str = br.readLine();

        int start = 0, end = 0, count = 1;

        alphabet[str.charAt(0) - 'a']++; // 첫의 인덱스를 alphabet에 반영

        while (end < str.length() - 1) {
            end++;
            if (alphabet[str.charAt(end) - 'a']++ == 0) count++; 

            // count가 N보다 크면 줄어들 때 까지 start를 앞으로 당김.
            while (count > N && start < end) { 
                if (--alphabet[str.charAt(start++) - 'a'] == 0) count--;
            }

            Ans = Math.max(Ans, end - start + 1);

        }
        System.out.println(Ans);
    }
}