[Algorithm] 백준 16472번_고냥이(Java)

🔗 16472번 고냥이

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

16472번: 고냥이

 

문제

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

 

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)

둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

 

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다.

 

💡 접근 방법 및 풀이

투 포인터 알고리즘 문제이다.

투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다. 풀이 방식을 보면 왜 투 포인터인지 알 수 있을 것이다.

 

풀이 방법

1. 알파벳 배열을 만든다.
2. 카운팅 변수, 결과 변수 생성
3. 배열의 하나의 인덱스를 가리키는 Start 점과 End 점 두 개를 만든다.(start는 시작 지점, End는 끝점을 가리킨다.)
   1. 처음 start와 end는 0으로 초기화해준다.
4. end를 기준으로 반복문 시작
   1. 알파뱃 배열의 값이 0이면? (새로운 알파벳이면?) 카운팅 + 1
   2. 만약, 카운팅 변수가 N 보다 크면 작거나 같을 때 까지 start 변수 + 1
      1. start 위치에 있는 알파벳 배열이 0이되면? 카운팅 변수 - 1
   3. 결과 값 중 큰 것 선택 (Math.max)

 

💻 코드

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

public class Main {
    static int[] alphabet = new int[26];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String string = br.readLine();

        int count = 0, answer = 0;

        for(int start = 0, end = 0; end < string.length(); end++) {
            if(alphabet[string.charAt(end) - 'a']++ == 0) {
                count++;
            }
            // count가 N보다 크면? 줄어들 때 까지 start 위치를 이동
            while (N < count && start < end) {
                if (--alphabet[string.charAt(start++) - 'a'] == 0) count--;
            }
            answer = Math.max(answer, end - start + 1);
        }
        System.out.println(answer);
    }
}