[백준] 3078 좋은 친구 c++

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

3078번: 좋은 친구

 

정답률 29%인데 한번에 맞춰서 기분이 너무 너무 좋았다 💞  💞 💞 💞 💞 💞 💞 💞 💞

처음에 문제 봤을때 떠오른 생각은 뒤에 있는 k명하고 길이를 비교하는 것을 생각했는데

골드 4가 그렇게 쉬울리가 없고 정답률이 낮아서 그 방법은 아닐 것 같았다. 시간제한 1초이기도 했고.

풀이

*큐에는 k+1개를 담을 수 있다. 비교할 등수 범위를 정해준다.

*배열 nameLength에는 해당 범위내(k+1)에 길이가 몇개씩 있는지 체크해준다. 

  ex) 현재 큐에  5가 2개 6이 1개 7이 1개가 있다면 배열의 상태는 아래 그림과 같다.

1.i 번째 친구의 이름의 길이를 큐에 담아준다. 

2.큐의 사이즈가 k+2개가 되면 큐를 pop해주고 배열에 해당하는 부분도 크기를 감소한다.

3. nameLength[nameSize]를 증가시켜준다. (새로 들어온 이름)

4. 현재 큐에 들어 있는 같은 nameSize와 각각 한 쌍을 이룰 수 있으므로   

 nameLength[nameSize]-1(자기자신 제외 )를 ans에 더해준다.

ex) 예제 1에서 큐에 3, 3이 들어있고 새로운 3이 들어오면 큐는 3,3,3이 들어있고  nameLength[3]=3이 된다.

새로운 2쌍이  생긴다. ->  (1번째 3,3번쨰 3) ,(2번째 3, 3번째 3)

4번째 친구의 이름의 길이가 3일때  큐에는 3개까지 담을 수 있으므로 앞에 3이 빠지고 새로운 3이 들어가서 

큐 : 3, 3, 3 배열 :  nameLength[3]=3  이 되고 ans에 2를 더해준다.ans +=nameLength[3]-1 

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

using namespace std;


queue<int>name;
int nameLength[21];
int N, K;
string temp;
int nameSize;
long long ans;
int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		nameSize = temp.length();
		name.push(nameSize);
		
		if (i > K)//큐에 k+2개 이상 담기게 되면 nameLength의 수를 하나 감소하고 큐를 pop해준다. 
		{
			if (nameLength[name.front()] > 0)
				nameLength[name.front()]--;
			name.pop();

		}
		
		nameLength[nameSize]++;
		if (nameLength[nameSize] > 0)
			ans+= (nameLength[nameSize]-1);
	
	}

	cout << ans;
}