[백준/C++] #16472 고냥이 (Two Pointer)

사실 어렵거나 함정이 있는 문제는 아니었는데... 그냥 문제 이름이 너무 귀여워서 포스팅한닷

문제

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

구상

최대 N개의 종류의 알파벳을 가진 연속된 문자열의 최대 길이를 구하는 문제였다. 

"연속된" 문자열의 길이라고 하니까 투 포인터로 접근할 수 있겠다 싶었다. 문자열의 인덱스값을 가리키는 lett와 right를 0부터 쭉쭉 나아가면서 left~right까지 사용하는 알파벳을 확인하면서 값 갱신하면 될듯했다. 

 

알고리즘

두개의 포인터를 이용하여 문제를 푸니까 Two pointer!!

 

풀이 + 코드

1. 사용하는 알파벳이 N개 미만이거나 N개라면, 값 비교후 갱신하고, right ++, 개수 확인

2. 사용하는 알파벳이 N개 초과라면, left++, 개수 확인

개수 확인 로직은 반복되니 따로 함수로 빼내어 호출했다. 

 

그리고, 알파벳을 숫자로 변경하는 부분이 필요했는데, 나는 char를 int로 바꿀 때 -'0'을 사용한다. 그래서 'a'-'0'을 출력해보았는데, 출력값으로 49가 나와서 - 49를 해주어 'a'가 인덱스 0을 의미하도록 하였다. 

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
using namespace std;
/*
16472 고냥이
최대 N개의 종류의 알파벳 가진 가장 긴 연속된 문자열의 길이는? 
*/

int N; // 1~26
string str;
int arr[26] = { 0, }; // 알파벳 배열. 0으로 초기화
int num = 1; // 초기값은 1
int count_alpha() {
    num = 0; // 초기화
    for (int i = 0; i < 26; i++) {
        if (arr[i] > 0) num++;
    }
    return num;
}
int res = 0;

void solution() { // right <= left
    int right = 0; int left = 0;
    arr[str[right] - '0' - 49]++;
    
    while (right < str.length()) {
        
        // N개 미만이거나 N개의 문자열을 사용하면, 값 비교후 갱신하고, right ++, 개수 확인
        if (num <= N) {
            res = max(res, right - left + 1);

            arr[str[++right] - '0' - 49]++; // 'a' -> 0
            num = count_alpha();
        }

        // N개 초과의 문자열을 사용하면, left++, 개수 확인
        else {
            arr[str[left++] - '0' - 49]--;
            num = count_alpha();
        }
    }
    
    cout << res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N;
    cin >> str;

    // 로직
    solution();

    return 0;

}