BOJ(백준) 3078 - 좋은 친구

---

아이디어 

이름의 길이가 상당히 제한적인 것을 보고, 자료구조의 기준을 이름의 길이로 잡아야 겠다는 아이디어를 떠올렸다. if(친구 && 좋은친구)의 기준은 이름의 길이가 같고, 성적의 등수가 K 이하로 나야 하니까, 이름의 길이가 같은 아이들끼리  자료구조에 담아두고, 자료구조에는 그 등수를 담아둔 다음, 정렬을 시킨 뒤, 이진탐색을 하여 좋은 친구의 쌍 수를 구하면 된다.

---

점검해볼 사항

- 이진탐색의 활용.

- 정렬을 시켜야하는 아이디어.

- 자료구조에 담기는 내용. int, pair

- 슬라이딩 윈도우, deque

---

시간복잡도

- Nlog(N) (= N만큼을 사용하여 길이를 인덱스로 가진 선형자료구조에 저장 + 20 * logN (길이는 최대 20이고 그 길이마다의 성적차순을 정렬해준다. + NlogN으로 모든 아이들기준으로 K만큼 차이나는 아이들의 쌍을 찾는다.)

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/3078.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define MAX_LEN 21
using namespace std;
typedef long long ll;
int main() {
    ll N, M, ans = 0;
    vector< vector<ll> > list;
    scanf("%lld%lld", &N,&M);
    list.resize(MAX_LEN);
    for (ll i = 1; i <= N; i++) {
        string s; cin >> s;
        list[s.size()].push_back(i);
    }
    for (ll i = 1; i <= 20; i++) {
        sort(list[i].begin(), list[i].end());
        for (ll j = 0; j < list[i].size(); j++) {
            ll idx = upper_bound(list[i].begin() + j, list[i].end(), list[i][j] + M) - (list[i].begin() + j);
            ans += (idx - 1);
        }
    }
    printf("%lld\n", ans);
    return 0;
}