[C++][백준 20437] 문자열 게임 2

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

풀이

각 알파벳(a~z)이 등장하는 위치를 저장해두고,

k개씩 묶어서 min값과 max값을 비교하여 갱신한다

 

만약 위치가 저장된 벡터의 사이즈(저장된 개수)가 k보다 작으면 그냥 넘긴다

이때, 모든 알파벳들이 전부 k보다 작으면 "-1"을 출력하기 위해 bool 타입 변수를 두어 이를 체크한다

 

각 알파벳마다 위치가 저장된 vector에서 길이 k의 윈도우를 한 칸씩 오른쪽으로 이동시켜가며 최대 최소값을 구해준다

위와 같은 방식이다

 

제출 코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t, k;
    string w;
    vector<int> v[26];
    cin >> t;
    while(t--)
    {
        int minStr = 10001;
        int maxStr = -1;
        bool e = true;
        cin >> w >> k;

        for (auto &a : v) a.clear();
        for (int i = 0; i < w.length(); i++)
            v[w[i] - 'a'].push_back(i);
        
        for (auto &a : v)
        {
            if (a.size() < k) continue;
            e = false; 
            for (int i = 0; i <= a.size() - k; i++)
            {
                int len = a[i + k - 1] - a[i] + 1;
                minStr = min(minStr, len);
                maxStr = max(maxStr, len);
            }
        }
        
        if (e) cout << "-1" << '\n';
        else cout << minStr << " " << maxStr << '\n';
    }
}

추가로... 단일 테스트 케이스에서는 전혀 문제되는 게 없었는데(k = 1, k=10000이나 문자열 길이가 10000인 경우 등의 케이스를 만들어서 시도해도 전부 맞았다) 이상하게 제출하면 틀리는 문제가 있었는데

vector 배열을 초기화하지 않아 생긴 문제였다...

이전 테스트 케이스가 누적되며 잘못된 결과를 출력하는 것이었다

 

vector를 초기화시켜주려면 두 가지 방법이 있는데

 

1. while loop 내부에서 vector를 선언해서 자동으로 loop를 돌며 초기화시키기

단, 이 경우는 테스트 케이스만큼 할당과 해제를 반복하게 되는 문제가 있다

 

2. clear를 통해 초기화

for loop를 돌며 각 vector를 초기화시켜줄 수 있다

이때 주의할 점은, for (int i = 0; i < 26; i++) v[i].clear(); 과 같은 코드로 초기화하면 문제없지만

내 코드처럼 for (auto a : v) a.clear(); 과 같이 초기화해서는 안 된다

 

for (auto a : v) 문을 사용하게 되면 변수 a에 값을 복사해서 넣은 후 사용하는 방식이기 때문에 a를 clear해봤자 v에는 영향이 가지 않는다

따라서 for (auto &a : v)와 같이 참조자를 작성해주어야 한다

꼭 초기화가 아니더라도 for 문에서 참조자를 작성해주면 복사하는 데 걸리는 자원을 아낄 수 있다는 장점이 있다