[백준] 3078번 좋은 친구 (C++)

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

 

 

이 문제는 좋은 친구가 되기 위해서 이름의 길이가 같아야 하고 등수의 차이가 K보다 작거나 같아야 하는데

이때 좋은 친구의 쌍의 개수를 구하는 문제이다.

 

처음엔 문제를 어떻게 접근해야할지 생각을 못했다 N의 크기가 30만 이기 때문에 길이가 같은 친구들끼리 묶은 후 모든 짝을 구해서

등수의 차이가 K이하인지 찾기에는 시간초과가 난다고 생각을 했다.

 

알고리즘 분류를 확인하니 큐, 슬라이딩 윈도우 구현방식을 확인하여 문제를 해결할 수 있었다.

 

 

문자열의 길이가 같은 친구들끼리 먼저 q에 넣는다 이때 현재 바라보는 문자가 큐에 가장 앞에 있는 인덱스의 차이가 K보다 작거나 같은 경우 이는 현재 i와 친구가 될 수 있는 쌍이기 때문에 계속해서 더해준다 하지만 K보다 큰 경우이는 같은 쌍이 될 수 없기에 K보다 작거나 같을때까지 앞에서 빼준다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int N, K;
queue<int> q[21];
int arr[300001];

void solve() {
    ll cnt = 0;

    for(int i = 1;  i <= N; i++) {
        while(!q[arr[i]].empty() && i - q[arr[i]].front() > K) q[arr[i]].pop();
        cnt += q[arr[i]].size();
        q[arr[i]].push(i);
    }

    cout << cnt;
}

void input() {
    cin >> N >> K;

    for(int i = 1; i <= N; i++) {
        string s;
        cin >> s;
        arr[i] = s.length();
    }
}

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

    input();
    solve();
}

 

 

회고록

구현하는 방법이 생각이 안나서 굉장히 시간이 오래걸렸던 문제이다. 좋은 친구의 쌍을 구하기 위해서

큐를 사용하여 현재 바라보는 친구가 가장 높은 등수의 친구의 차이와 비교해서 쌍을 맺는것이 굉장히 

낯선 테크닉이였던 것 같다.