백준 3078 (좋은 친구) c++

문제

3078번: 좋은 친구

친구들의 이름을 성적 순대로 입력 받고 성적 순위가 k이하로 되고 이름의 길이가 같은 친구의 수를 세는 문제입니다.

단순히 naive하게 이중 for문을 사용하면 시간복잡도가 O(n^2) 이 발생하기 때문에 다른방법을 생각해주어야 합니다.

따라서 입력받은 이름을 문자열의 길이로 변환해 QUEUE에 넣어줍니다. 

QUEUE는 가장 먼저 들어온게 맨 앞으로 가고 늦게 들어오면 뒤로 들어가므로 

각각의 문자열의 길이에 맞는 QUEUE 배열 인덱스에 모두 저장해 

QUEUE 각 인덱스의 원소가 성적이 됩니다. 

따라서 QUEUE의 각 원소가 k 보다 작을 때까지 계속 없애주고 남아있는 QUEUE 해당 인덱스의 원소의 개수를

더해주면 됩니다. 

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

 먼저 학생들의 수 n과 성적 순위 차이의 기준 k를 입력 받아줍니다.

long long cnt = 0;

변수 cnt는 좋은친구를 세는 변수입니다.

사실 이 코드 때문에 많이 틀렸습니다.

처음에는 int cnt = 0; 이라고 했는데 계속 틀렸습니다....

n이 최대 300000 까지 입력받을 수 있으므로 

worst case는 cnt += 300000 + 299999 + 2999998 + ......  가 됩니다.

그렇게 되면 cnt는 int형의 범위를 넘어가게 되므로 오류가 발생합니다.

따라서 long long 형으로 입력받으면 문제가 해결됩니다.

queue<int>q[25];
for (int i = 0; i < n; i++) {
	string st;
	cin >> st;
	int len = st.length();
	while (!q[len].empty() && i - q[len].front() > k)
		q[len].pop();
	cnt += q[len].size();
	q[len].push(i);
}
cout << cnt;

여기서 QUEUE q[25]를 선언했는데 이름의 길이는 최대 20글자 까지 받을 수 있으므로 

QUEUEU 배열의 크기를 넉넉하게 25까지 잡아줬습니다.

QUEUE 배열 각 인덱스에는 해당 문자열의 길이를 의미합니다. 

예를 들어 q[2] ={1, 2, 5, 8} 라고 하면 이름이 2글자인 사람이 4명 있다는 의미이고 각 1등, 2등, 5등, 8등의 이름이

2글자라는 의미입니다.

이제 for문을 살펴보면 변수 len은 입력받은 이름의 길이를 의미합니다.

while 문은 q의 len 번째 인덱스가 empty 상태가 아니며 i가 현재 등수를 의미하므로

(현재등수 - q에 저장된 가장 오래된 원소의 등수) 가 k보다 크면 필요없으므로 while문이 반복될때 까지 pop 해줍니다.

while문을 벗어나면 남아있는 q[len]의 원소의 개수는 좋은 친구이므로 cnt에 더해줍니다.

그리고 i가 현재 등수를 의미하므로 마지막에 q에 넣어줍니다.

---

전체코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	ll cnt = 0;
	
	queue<int>q[25];
	for (int i = 0; i < n; i++) {
		string st;
		cin >> st;
		int len = st.length();
		while (!q[len].empty() && i - q[len].front() > k)
			q[len].pop();
		cnt += q[len].size();
		q[len].push(i);
	}
	cout << cnt;

	return 0;
}