백준 3078: 좋은 친구 [C/C++]

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

3078번: 좋은 친구

#include <iostream>
#include <string>
using namespace std;
int n, k;
long long ans; // IntMax < 300000 * 300000
int lis[666666]; // n + k <= 600000
int cnt[22];
void input() {
    string s;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> s;
        lis[i] = s.size(); // 길이를 입력한다.
    }
}
void solve() {
    for (int i = 0; i <= k; i++) cnt[lis[i]]++; // k번째 까지의 이름의 길이를 저장한다.
    for (int i = 0; i < n - 1; i++) {
        cnt[lis[i]]--; // 자기 자신은 친구가 될 수 없다.
        ans += cnt[lis[i]];
        cnt[lis[i + k + 1]]++; // i가 ++되며 자신과 등수가 k 차이나는 친구의 이름의 길이를 더 해준다.
    }
    cout << ans;
}
int main() {
    input();
    solve();
    return 0;
}
 

풀이:

슬라이딩 윈도우 문제입니다.

k번째 까지의 이름의 길이를 저장하고, 자기 자신은 친구가 될 수 없으니 길이를 저장한 배열에서 빼줍니다.

그리고 매번 등수가 늘 때 마다, i++가 되니 자신과 등수가 k 차이나는 친구의 이름의 길이를 더 해 줍니다.