[백준] #3078 좋은 친구(c++)

좋은 친구

처음 배열로 풀었는데 시간초과가 났다. (시간제한이 1초고 n이 300000까지라서)

배열로 푼 코드

#include <iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k,ans=0;
    string str[300000];

    cin >> n >> k;
    for (int i = 0; i < n;i++){
        cin >> str[i];
    }

    for (int j = 0; j < n; j++){
        for (int l = j + 1; l < n; l++){
            if((str[j].length()==str[k].length()) && (l-j)<=k )
                ans++;
            
        }
    }
    cout<<ans;
}

그래서 큐를 이용해 푸는 방식으로 수정했다.

큐를 이용한 코드

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

using namespace std;

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

	int n, k;
    string str;
	queue<int> que[21];
	long long ans=0;

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

		int len = str.length(); //이름의 길이
       
        while (!que[len].empty() &&  i - que[len].front()> k) { //이름의 길이에 맞는 큐가 비어있지않고 등수 차이가 k보다 크면
			que[len].pop();									 //맨 앞에있는 애 빼기
		}
		ans += que[len].size(); //큐에 들어있는 개수 더하기
		que[len].push(i);

	}

	cout << ans;
}