[백준 JAVA] 16472. 고냥이

문제 링크

---

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

접근 방법

---

투 포인터를 사용합니다.

몇 종류의 문자를 썼는지와 각 문자를 몇 개씩 사용했는지 세어줍니다.

사용한 문자가 N을 넘었으면 왼쪽 포인터를 사용한 문자 종류가 감소할 때까지 옮깁니다.

소스 코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 최대 문자 수
        int max = Integer.parseInt(br.readLine());
        String str = br.readLine();
        
        // 답을 저장할 변수, 고유 문자 수를 셀 변수, 시작과 끝 포인터
        int answer = 0, cnt = 0, s = 0, e = -1;
        int[] alpha = new int[26]; // 각 문자의 빈도를 저장할 배열

        while (++e < str.length()) { // 문자열의 끝까지 e 포인터를 이동
            if (alpha[str.charAt(e) - 'a']++ == 0) { // e 위치의 문자를 배열에 추가
                ++cnt; // 문자 종류 수 증가
            }

            // 고유 문자 수가 max를 초과하면 s 포인터를 이동
            while (max < cnt) {
                if (--alpha[str.charAt(s++) - 'a'] == 0) { // s 위치의 문자를 배열에서 제거
                    --cnt;
                }
            }

            answer = Math.max(answer, e - s + 1);
        }

        System.out.println(answer);
    }
}

 

코드 설명

---

e 포인터를 문자열의 끝까지 오른쪽으로 이동시키면서

해당 인덱스 문자의 빈도가 0이면 문자 종류 수인 cnt를 증가시킵니다.

만약 cnt가 max를 초과하게 되면, s 포인터를 오른쪽으로 이동시킵니다.

이때, s 인덱스의 문자 개수를 감소시키며, 해당 문자의 빈도가 0이 되면 cnt를 감소시킵니다.