백준 16472번 고냥이 [C++]

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

16472번: 고냥이

#문제 해결 방법

투 포인터를 사용하자

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int st = 0, en = 0;
    int maxLength = 0;
    int curType = 0;

    int alpha[26] = { 0, };

    while (en < s.length()) {
        if (alpha[s[en] - 'a'] == 0) curType++; // 새로운 알파벳 타입을 발견
        alpha[s[en] - 'a']++;

        while (curType > n) { // 허용된 타입을 초과하면 앞에서부터 제거
            if (--alpha[s[st] - 'a'] == 0) curType--;
            st++;
        }

        maxLength = max(maxLength, en - st + 1); // 최대 길이 갱신
        en++;
    }

    cout << maxLength << endl;

    return 0;
}

#코드 설명

 

1. 변수 설정
   • int st = 0, en = 0; : 투 포인터 알고리즘에서 사용할 시작 포인터(st)와 끝 포인터(en)를 초기화합니다.
   • int maxLength = 0; : 최대 문자열 길이를 저장할 변수입니다.
   • int curType = 0; : 현재 연속된 문자열에서의 알파벳 종류의 수를 저장합니다.
   • int alpha[26] = { 0, }; : a부터 z까지의 알파벳이 현재 연속된 문자열에서 몇 번 나타났는지를 저장하는 배열입니다.
2. 투 포인터 알고리즘
   • while (en < s.length()) : 끝 포인터(en)가 문자열의 길이보다 작은 동안 반복합니다.
     • if (alpha[s[en]-'a'] == 0) curType++; : 끝 포인터가 가리키는 알파벳이 현재 연속된 문자열에 처음 등장하면 알파벳 종류의 수(curType)를 1 증가시킵니다.
     • alpha[s[en]-'a']++; : 해당 알파벳의 등장 횟수를 1 증가시킵니다.
     • while (curType > n) : 알파벳 종류의 수가 N을 초과하면, 시작 포인터를 하나씩 이동시키면서 초과된 알파벳 종류의 수를 줄입니다.
     • maxLength = max(maxLength, en - st + 1); : 최대 문자열 길이를 갱신합니다.
     • en++; : 끝 포인터를 1 증가시킵니다.