[백준] 3078번: 좋은 친구

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

3078번: 좋은 친구

큐 연습문제. 풀이를 보고 구현했다.

그냥 배열로 풀면 시간복잡도가 O(N^2)이 되는데 N이 300,000 이하이므로.. 배열로는 풀면 안될 것 같은 예감이 바로 든다(실제로 배열로 풀면 시간초과가 뜸)

 

이 문제를 풀기 위해 이름 길이별로 큐를 만든다. (큐에 저장되는 정보는 학생의 인덱스(등수)이다.)

그리고 각 학생을 입력받을 때마다 이름 길이에 해당하는 큐를 탐색한다.

인덱스의 차이가 k보다 큰 학생들을 모두 pop한 뒤에,

남아있는 큐의 원소 개수를 카운트하고 새로 입력된 학생의 인덱스를 push하면 된다.

 

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

using namespace std;

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

	int n, k;
	queue<int> q[21];
	long long cnt = 0;

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

		int len = input.length();

		while (!q[len].empty() && i - q[len].front() > k) {
			q[len].pop();
		}
		cnt += q[len].size();
		q[len].push(i);
	}

	cout << cnt;
}

 

정답코드