[BOJ 16472] 고냥이 (Java, 투포인터)

 

 

 

---

문제 링크

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

16472번: 고냥이

---

풀이

- 알파벳(26자) 카운팅 배열을 활용하여 투포인터 문제 풀이

- 시간복잡도는 O(N) 

*알파벳 인덱스 구하기
int index = TEXT.char(i) - 'a';

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, CNT;
    static String TEXT;

    static int[] ALPHABET = new int[26];

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        TEXT = st.nextToken();
    }

    static void add(int i) {
        int idx = TEXT.charAt(i) - 'a';
        ALPHABET[idx] += 1;
        if(ALPHABET[idx] == 1) CNT += 1;
    }

    static void remove(int i) {
        int idx = TEXT.charAt(i) - 'a';
        ALPHABET[idx] -= 1;
        if(ALPHABET[idx] == 0) CNT -= 1;
    }

    static void pro() {
        int ans = 0; // ans : 최대 길이

        for(int L = 0, R = 0; R < TEXT.length(); R++) {
            add(R);

            while(CNT > N) {
                remove(L);
                L += 1;
            }

            ans = Math.max(ans, R - L + 1);
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}