[Java] 백준 16472번 : 고냥이

문제

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

 

접근 방법

1. 문자열에서 인식할 수 있는 알파벳 종류가 N일때 N개의 언어로 이루어진 수열의 최고 길이를 구하는 문제이다.
2. 이 문제는 브루트포스로 구할 수 있지만 시간 초과가 발생한다. O(N^2) 10만 *10만 = 100억
3. 따라서 반복문 하나를 줄일 수 있는 방법인 투 포인터를 생각하였다.
4. 코드를 보는 것이 조금 더 이해가 쉬울 것이다.

접근 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N;
    private static String line;
    private static int[]alphabet = new int[26];
    private static int max = Integer.MIN_VALUE;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

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

        line = br.readLine();
        alphabet[line.charAt(0)-'a']++;
    }

    //실행
    public static void process() {
        int s = 0;
        int e = 0;
        int cnt = 1;

        while(true){
            e++;

            if(e == line.length()){
                break;
            }

            int num = line.charAt(e)-'a';
            alphabet[num]++;
            
            //문자가 총 몇개 사용됐는지 체크
            if(alphabet[num] == 1){
                cnt++;
            }

            //만약 문자가 N개를 초과한다면 s포인터를 옮겨줘야한다.
            while(cnt > N){
                int temp = line.charAt(s)-'a';
                alphabet[temp]--;

                if(alphabet[temp] == 0){
                    cnt--;
                }

                s++;
            }

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

        System.out.println(max);
    }


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