백준 3078: 좋은 친구

문제 요약

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

문제 분류

• 자료 구조
• 슬라이딩 윈도우
• 큐

문제 풀이

문자열의 길이별로 큐를 준비하고, 인덱스 번호를 삽입하면 된다.

큐의 앞의 인덱스가 새로 삽입될 인덱스 번호와의 차가 k를 넘을 경우 삭제해 나가고, 남은 큐의 사이즈만큼 카운트에 누적시키면 된다. 즉, 큐에 남은 인덱스들이 새로 삽입될 인덱스의 '좋은 친구'가 된다.

정답이 int범위를 벗어남에 주의하자

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
	int n, k, len;
	long long cnt = 0;
	string in;
	queue<int> q[21];
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> in;
		len = in.length();
		while (!q[len].empty() && ((i - q[len].front()) > k)) q[len].pop();
		cnt += q[len].size();
		q[len].push(i);
	}
	printf("%lld", cnt);
	return 0;
}