[백준] 16472 고냥이 - Java

 

 

 

문제 출저

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

16472번: 고냥이

 

 

 

문제 풀이

인식할 수 있는 알파벳의 종류 n과 문자열이 주어집니다. 문자열에서 인식할 수 있는 최대의 길이를 구해야 합니다. 

 

투 포인터를 이용해 풀었습니다. 

어떤 알파벳이 몇 개 나왔는지 세기 위한 int[] counts = new int[26]; 일차원 배열을 이용했습니다. 알파벳 갯수는 26개 이므로 배열의 크기를 26으로 설정했습니다. 

int start = 0, int end = 1 인 두 개의 포인터를 이용했습니다. start, end 구간의 알파벳 갯수를 counts 배열에 저장했습니다. 알파벳의 종류가 n 이하일 때는 end를 하나씩 늘립니다. 그러다 알파벳 종류가 n을 넘으면 start++ 땡겨 구간을 줄였습니다.

이런 식으로 투 포인터 탐색을 진행하여 조건에 맞는 구간마다 더 높은 구간값을  update 하여 답을 구할 수 있었습니다.

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int[] counts = new int[26];

        int count = 0;
        int answer = 0;

        int s = 0;
        int e = 1;

        int startNumber = change(str.charAt(s));
        if(counts[startNumber] == 0) {
            count++;
        }
        counts[startNumber] += 1;

        int endNumber = change(str.charAt(e));
        if(counts[endNumber] == 0) {
            count++;
        }
        counts[endNumber] += 1;

        while(true) {

            boolean flag = false;

            e++;
            endNumber = change(str.charAt(e));
            if(counts[endNumber] == 0) {
                count++;
                if(count > n) flag = true;
            }
            counts[endNumber] += 1;

            while(flag) {
                startNumber = change(str.charAt(s));
                counts[startNumber] -= 1;
                if(counts[startNumber] == 0) {
                    count--;
                    if(count <= n) flag = false;
                }
                s++;
            }

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

            if(e == str.length()-1) break;

        }

        System.out.println(answer);

    }

    public static int change(char c) {
        return (int) c - 'a';
    }

}