[백준] 3078 좋은 친구

백준 3078 좋은 친구

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

• 첫 번째 코드 (시간 초과)

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


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


	int n, k;
	cin >> n >> k;

	//이름의 길이 저장
	vector <int> name;

	string input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		name.push_back(input.size());
	}
	
	long long cnt = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 1; j <= k && i + j < n; j++)
			if (name[i] == name[i + j])
				cnt++;
	
	cout << cnt;
	return 0;
}

풀이

• 슬라이딩 윈도우 기법 사용

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


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


	int n, k;
	cin >> n >> k;

	//이름의 길이
	vector <int> name;

	string input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		name.push_back(input.size());
	}
	
	
	long long cnt = 0;
	for (int len = 2; len <= 20; ++len) {
		//구간 내 이름의 길이가 len인 학생의 수
		long long rangecnt = 0;
		for (int i = 0; i < k; ++i)
			if (name[i] == len) rangecnt++;

		//슬라이딩 윈도우
		for (int i = 0; i < n; ++i) {
			if (i + k < n && name[i + k] == len) rangecnt++;
			if (name[i] == len) {
				rangecnt--;
				cnt += rangecnt;
			}
		}
	}
	
	cout << cnt;
	return 0;
}