3078번 좋은 친구

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

3078번: 좋은 친구

 

큐와 슬라이딩 윈도우 기법을 사용하였다.

1. 자기 글자수에 맞게 큐에 넣어준다.

2. 순위가 높은순으로 큐에 들어간다.

3. (제일 나중에 들어온 순위 - 큐 가장 앞에 있는 순위)가 k를 초과하면 가장 앞에 있는 순위를 빼준다. -> 슬라이딩 윈도우 기법

 

주의해야 할 점은 만약 n = k = 300000이면 쌍이 (299999 * 300000 / 2) 개가 만들어지므로 int 범위를 넘어간다.

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define INF 2e9
#define F first
#define S second
using namespace std;

typedef long long l;
typedef pair<int,int> p;
typedef tuple<int,int,int> tu;
typedef vector<int> vc;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    string s;
    int n,k;
    l ans = 0;
    queue<int> q[22];

    cin >> n >> k;

    for(int i=0;i<n;i++){
        cin >> s;

        int size = int(s.size());

        while(!q[size].empty() && i - q[size].front() > k)
            q[size].pop();

        ans += int(q[size].size());
        q[size].push(i);
    }

    cout << ans;

}