[백준/BOJ] 백준 3078번 : 좋은 친구

www.acmicpc.net/problem/3078

3078번: 좋은 친구

이름의 크기 별로 따로 큐 만들어 관리하여, 해당 이름이 들어올 때 그 이름 크기의 큐에 지금 들어오는 이름과 등수 차이가 k보다 큰 거는 pop을 통해 지운다 즉 큐에 있는 모든 것들과 등수 차이가 k이하가 되도록 만들어서 현재 이름이 해당 큐에 있는 모든 것들과 좋은 친구가 될 수 있도록 만드는 방법을 통해 문제를 해결했다.

 

코드

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

int n, k;
vector<string> name;
queue<int> name_q[21]; //이름의 크기 별로 큐에 들어온 순서대로 인덱스를 저장한다
long long result = 0;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		name.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		string this_name = name[i];
		int this_name_size = this_name.size();

		while (1)
		{
			if (name_q[this_name_size].empty())
				break;

			int front_index = name_q[this_name_size].front();

			//큐에 있는 모든것들과 등수 차이가 k이하일때
			//즉, 현재 i번째 이름이 해당 큐에 있는 모든것들과 좋은 친구가 될 수 있을때 
			if (i - front_index <= k)
				break;

			//등수 차이가 k보다 큰거는 지운다
			name_q[this_name_size].pop();
		}

		//현재 i번째 이름이 큐에 저장되어 있는 것들과 좋은 친구 쌍이 되는 경우
		result += name_q[this_name_size].size();

		name_q[this_name_size].push(i);
	}

	cout << result;

	return 0;
}