[Algorithm] 백준 3078 좋은 친구 - C++, deque

3078번: 좋은 친구

#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;

int numberofStudent, rankDifference;
vector<int> rankToLength;
deque<int> lengthToRank[21];

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // input
    cin >> numberofStudent >> rankDifference;
    rankToLength.resize(numberofStudent);

    for(int i = 0; i < numberofStudent; i++){
        string studentName;
        cin >> studentName;
        rankToLength[i] = studentName.length();
    }

    // calculate
    long long answer = 0;
    for(int rank = 0; rank < numberofStudent; rank++){
        auto& curNameGroup = lengthToRank[rankToLength[rank]];
        curNameGroup.push_back(rank);

        if(curNameGroup.size() == 1)    continue;

        while (rank - curNameGroup.front() > rankDifference){
            curNameGroup.pop_front();
        }
        answer += curNameGroup.size() - 1;
    }

    cout << answer << '\n';
}

---

일단 N^2으로 하면 시간이 부족할 거 같아서 위 코드와 같은 방법을 사용했습니다. 일단 입력에서 각 학생 등수에 맞는 이름 길이를 저장을 했습니다. 이후 계산을 하면서 deque를 사용했는데 여기서 deque는 '해당 이름 길이를 가진 학생 수'를 의미합니다. 때문에 이 그룹에서 문제에 주어진 K(위 코드에서는 rankDifference)보다 등수 차이가 난다면 deque에서 제외를 해주면서 천처히 계산하는 것입니다.