[백준] 16472: 고냥이

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

16472번: 고냥이

시간복잡도는 O(N), 선형적으로 진행하기 위해서 투 포인터(Two Pointers)라는 알고리즘으로 문자열을 탐색해나간다.

해당 문자열 안의 알파벳 종류의 수를 확인할 때 매번 탐색하면 비효율적이기 때문에 별도의 변수(cnt)를 통해 기록한다.

여기서 간과하였던 점은 head와 tail을 오고갈 때, 문자열에 포함된 문자의 종류를 체크하기 위해서 set을 사용하려 했다.

그런데 현재 문자열에 포함된 문자가 여러 개 있는 경우를 고려해야 했다.

 

1차원 배열에 문자열에 포함된 해당 문자의 개수를 기록하여, head에 있는 문자가 다른 위치에도 있으면 문자 종류의 개수는 그대로 유지되도록 할 수 있고, 또한 tail에 있는 문자가 다른 위치에도 있어도 문자 종류의 개수는 그대로 유지되도록 한다.

 

이 문제를 풀면서 힘들었던 점은, 생각한 코드가 어떤 위치에 존재해야하는지를 결정하기 어려웠다.

최대 문자열의 길이를 갱신하는 코드를 맨 뒤에 두었다가 낭패를 보았다.

왜냐하면 내 코드 상 다음 탐색을 위한 인덱스 조절을 앞에서 이미 끝냈기 때문이다.

그래서 내가 개발한 내용을 까먹지 않도록 적절히 주석을 다는 습관도 중요하다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> alphabets(26, 0);
int main(void) {
    int n, head = 0, tail = 0, answer = 0, cnt = 0;
    string str;
    cin >> n;
    cin >> str;
    while(tail <= str.length() - 1 && head <= tail) {
        // tail에 해당하는 문자가 head ~ tail 사이에 있으면
        // 알파벳 종류의 개수는 증가하지 않기 때문
        if(!alphabets[str[tail] - 'a']) {
            cnt++;
        }
        alphabets[str[tail] - 'a']++;
        if(cnt <= n) {
            if(answer < tail - head + 1) {
                answer = tail - head+1;
            }
            tail++;
        }
        else {
        	// 이 경우는 문자열 길이가 줄어드는 과정이므로 answer 갱신 코드 불필요
            while(cnt > n) {
                // head에 해당하는 문자가 head ~ tail 사이에 있으면
                // 알파벳 종류의 개수는 감소하지 않기 때문
                alphabets[str[head] - 'a']--;
                if(!alphabets[str[head] - 'a']) {
                    cnt--;
                }
                head++;
            }
            tail++;
        }
    }
    cout << answer << '\n';
}