[백준 3078] 좋은 친구

문제

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

 

알고리즘

구현

 

풀이

위치가 K+1이상 벗어나지 않으면서 이름의 길이가 같은 쌍의 갯수를 찾는 문제입니다.

 

$N$제한이 30만이므로 $O(N^2)$을 사용해서 순서쌍을 찾기는 어렵습니다. 스택과 비슷한 느낌으로 현재 자신과 같은 길이가 이전에 몇개 있었는지를 기록하여 $O(N)$에 풀도록 합시다. 단 이것을 기록한 배열은 유효한(서로 친구)값만을 유지하기 위해서 위치 차이가 K가 넘어가면 해당 정보를 지우는 업데이트를 하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 3e5 + 5;

int N, K;
int c[21], nm[MAXN];
long long ans;
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> K;
    rep(i, N) {
        string s;
        cin >> s;
        nm[i] = s.length();
    }
    rep(i, N) {
        if (i >= K + 1) c[nm[i - K - 1]] -= 1;
        ans += c[nm[i]];
        c[nm[i]] += 1;
    }
    cout << ans;
    return 0;
}