(C++) - 백준(BOJ) 3078번 : 좋은 친구

www.acmicpc.net/problem/3078

3078번: 좋은 친구

이분탐색 문제였습니다.

 

풀이방법

 1. map 자료구조 m을 선언합니다. key엔 이름길이, value는 해당 이름길이를 가진 학생들의 등수들이 담긴 vector입니다.

 

 2. m의 크기만큼 loop를 돕니다. 매 이름 길이마다 좋은 친구의 순서쌍을 변수 ans에 더해줍니다. 현재 index에서 k만큼 더한 v[i] + k를 초과하는 등수를 가진 친구가 처음나오는 index를 찾습니다. 찾게 된다면 그 이전 index의 친구들과 자신의 위치 사이는 무조건 좋은 친구가 됩니다. 찾은 index -1 - i가 곧 쌍의 개수가 됩니다.

 

 3. ans를 출력합니다.

 

* k가 30만이고 n이 30만인 경우 학생의 이름길이가 다 똑같다면 30만 + 29만9999 + .... + 1의 형식으로 int범위가 넘는 쌍의 개수가 나올 수 있으므로 자료형을 long long으로 선언해줍니다.

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k, ans;
map<ll,vector<ll>> m;
int main(){
    cin >> n >> k;
    for(ll i = 0; i < n; i++){
        string s;
        cin >> s;
        m[s.size()].push_back(i);
    }

    for(auto &el : m){
        vector<ll> v = el.second;
        sort(v.begin(),v.end());
        for(ll i = 0; i < v.size(); i++){
            ans += upper_bound(v.begin(),v.end(),v[i]+k) - (v.begin() + i + 1);
        }
    }

    cout << ans <<'\n';

}