[백준 20437] - 문자열게임 2(슬라이딩 윈도우) C++

문제

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

20437번: 문자열 게임 2

접근방법

k의 개수만큼 배열의 크기를 유지하는 게 포인트라고 생각했다.

각 알파벳마다 인덱스를 저장할 배열이 필요했고, 그 배열의 크기는 k로 일정했으면 좋겠다는 생각이 들어서 queue를 선택했다.

 

각 알파벳마다 queue를 만들었다면, queue에 k개의 원소가 채워질 때마다 첫번째 인덱스와의 거리를 계산한후 push, pop해주면 된다.

그러면 queue의 크기를 항상 k로 유지할 수 있다.

 

이 방법을 슬라이딩 윈도우라고 부르는 것 같다.

나는 큐를 사용했는데, vector를 사용한 사람도 있다.

vector를 사용한다면, k번째 앞에 있는 원소와 비교해야할 것이다.

그런 점에서 queue를 사용하는 것이 더 편리하다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define FASTERIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 987654321
int k;

int get_shortest(string game) {
    vector<queue<int>> bowl(26, queue<int>());
    int ret = MAX;

    FOR(i, game.size()) {
        int idx = game[i] - 'a';
        //큐 사이즈가 k인 경우, 맨 앞 원소와의 거리 계산.
        if (bowl[idx].size() == k-1) {
            bowl[idx].push(i);
            ret = min(ret, i - bowl[idx].front() + 1);
            bowl[idx].pop();
        } else {                //큐사이즈가 k보다 작은 경우 push
            bowl[idx].push(i);
        }
    }
    return ret;
}

int get_longest(string game) {
    vector<queue<int>> bowl(26, queue<int>());
    int ret = -1;

    FOR(i, game.size()) {
        int idx = game[i] - 'a';
        //큐 사이즈가 k인 경우, 맨 앞 원소와의 거리 계산.
        if (bowl[idx].size() == k-1) {
            bowl[idx].push(i);
            ret = max(ret, i - bowl[idx].front() + 1);
            bowl[idx].pop();
        } else {                //큐사이즈가 k보다 작은 경우 push
            bowl[idx].push(i);
        }
    }
    return ret;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        string game;
        cin >> game >> k;
        int shortest = get_shortest(game);
        int longest = get_longest(game);
        if (shortest == MAX || longest == -1) cout << -1 << endl;
        else cout << shortest << " " << longest << endl;
    }

    return 0;
}

개선할 점

..