[BOJ_16472] 고냥이 Java (투 포인터)

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

16472번: 고냥이

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

public class Main {

    static int n;
    static int maxLength = 0;
    static int[] check = new int[26]; // 알파벳 몇번 나왔는지 기록
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        char[] arr = br.readLine().toCharArray();

        int start = 0;
        int end = 0;
        int count = 1; // 지금까지 나온 알파벳 종류 수
        check[arr[0]-'a'] = 1;

        while(true) {
            end++;

            // 종료 조건: 끝까지 봤음
            if(end == arr.length) {
                break;
            }

            int right = arr[end] - 'a';
            check[right]++;

            if(check[right] == 1) {
                count++;
            }

            // 알파벳 종류가 n보다 큰 상태
            while(count > n) {
                // start를 앞으로 한칸 옮길 것

                int left = arr[start] - 'a';
                check[left]--;

                // 이제 check[left] 알파벳은 문자열에 없음
                if(check[left] == 0) {
                    count--;
                }

                start++;
            }

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

        System.out.println(maxLength);
    }
}

1차원 배열에서 두 개의 포인터를 두고 조작하여 원하는 값을 알아내는 투 포인터 알고리즘을 활용하는 문제입니다.
이 문제에서 투 포인터를 사용하지 않고 모든 부분 배열을 완전 탐색한다면 O(n^2)이 되고 시간초과가 될 것입니다.

 

 

투 포인터 개념 정리는

https://aainy.tistory.com/5

투 포인터 (Two Pointers)

포스팅에 있습니다 ^_^