[BOJ]3078 - 좋은 친구 (C++)

문제

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

코드

방법#1

#include <iostream>
#include <queue> 
#include <array> 

using namespace std; 

int main(void){
    cin.tie(0);cout.tie(0);
        ios_base::sync_with_stdio(false);

    int n, k;
    long long sumNum=0; 
    int outNum;
    string name; 
    queue<int> q;
    int arr[21] = {};   //큐 내에 있는 이름 길이 배열 

    cin >> n >> k; 

    //큐 초기화 
    for(int i=0; i<k; i++){
        q.push(1);
    }

    for(int j=0; j<n; j++){
        cin >> name; 

        int length1 = name.length(); 
        sumNum += arr[length1];

        outNum = q.front();
        q.pop();
        q.push(length1);
        arr[outNum]--;
        arr[length1]++;
    }
    cout << sumNum; 
}

방법#2

#include<iostream>
#include<vector>
#include<queue>
#include<string>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<string>v;
    queue<int>q[21];
    v.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    long long res = 0;
    for (int i = 1; i <= n; i++) {
        int len = v[i].length();
        while (!q[len].empty() && i - q[len].front() > k)
            q[len].pop();
        res += q[len].size();
        q[len].push(i);
    }
    cout << res;
    return 0;
}

풀이

방법#1

먼저 큐를 생성한 뒤에 1로 초기화 해주었다.
이 큐에는 학생들의 이름의 길이를 넣을 예정인데 이름의 길이가 2~20이라고 해서 1로 초기화하였다.
배열은 arr는 이름의 길이를 인덱스로 하고 배열 내에는 큐에 있는 이름의 길이의 수를 넣는다.
예를 들어 큐의 길이(K)가 3이고 큐의 초기화한 상태가 [1,1,1]이라면 arr[1] = 3이다.
sumNum은 친구의 쌍의 개수이다.
현재 큐에 있는 원소들 중 같은 길이의 아이들이 '좋은 친구'니까 해당 배열에 있는 수를 sumNum에 더한다.

방법#2

이 방법은 우리 동아리 스터디장님의 코드이다.
큐를 21개 만들고 벡터에는 아이들의 이름을 넣는다.
위의 방법의 arr와 같이 이 큐도 아이들의 이름의 길이로 구별된다.
i번째에서 q[len].front()를 뺀 것이 등수 차이인 k보다 크다면, 그 아이들은 좋은 친구가 될 수 없기 때문에 pop해준다.
아닐 경우에는 결과 값에 큐의 크기를 더해준다.

---

이 문제는 사실 너무 어려워서 한참을 고민하다가 친구에게 물어보기도 하고(#1) 구글의 여러 코드들을(#2) 찾아보기도 했다😭
나같은 실버 나부랭이에게는 진짜 어려웠다....