[백준] 좋은 친구

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

3078번: 좋은 친구

슬라이딩 윈도우를 이용하는 문제입니다. 

 

문제부터 간단하게 요약하면, 성적 순으로 학생들의 이름이 주어지면, 좋은 친구의 쌍 수를 구해야 하는 문제입니다.

여기에서 좋은 친구라는 것은 등수 차이가 K를 넘지 않고, 이름의 길이가 같아야 합니다. 

 

<Solution>

이름 길이가 2글자에서 20글자 사이이기 때문에, 

이름 길이를 이용한 array를 만들어 두고, window를 움직이면서 계산을 해주면 됩니다.

 

조금 더 살펴보면,

int name_length[21];

위와 같이 이름 길이를 index로 하고, element는 해당하는 index만큼의 길이를 가진 원소 수로 하는 name_length array를 만들고, window를 뒤로 밀면서 빼고 더하고를 하면서 계산하면 구현이 가능합니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <string>
 
using namespace std;
 
#define MAX_N (300000)
 
int N, K;
string name[MAX_N + 10];
 
void Input_Data(void) {
    string str;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> name[i];
    }
}
 
int name_length[21];
long long solution(){
    long long cnt = 0;
    // initial window
    int tmp = name[0].length();
    for(int i = 0; i<K+1; i++){
        name_length[name[i].length()] ++;
    }
    cnt+= (name_length[tmp]-1);
    for(int i = 1; i<N; i++){
        name_length[name[i-1].length()] -=1;
        if(i+K < N) name_length[name[(i+K)].length()] +=1;
 
        tmp = name[i].length();
        cnt+= (name_length[tmp]-1);
    }
    return cnt;
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    long long sol = -1;
 
    // 입력 받는 부분
    Input_Data();
 
    // 여기서부터 작성
    sol = solution();
 
    // 출력하는 부분
    cout << sol << '\n';
 
    return 0;
}