[백준] 3078번 좋은 친구

3078번: 좋은 친구

처음부터 끝까지 비교하면서 카운트하다 시간 초과 나서 여러 번 피 본 문제이다.

정렬도 하고 조건문 달아서 최소한으로 비교해줘도 시간 초과 밖에 안 나서

방법을 아예 다르게 해 보았다.

 

등수	1	2	3	4	5	6
이름의 길이	7	7	6	7	7	6

 

입력이 이런 상태이고 K는 3이라 가정할 때,

 

이름의 길이를 첫 index로 가지는 이차원 벡터를 정의해 준 뒤

입력을 받으면서 이름의 길이가 똑같은 아이들이 2명 이상일 경우(v[index].size>=2)에만

등수의 차를 비교해준다.

 

등수	1	2	3	4	5	6
이름의 길이	7	7	6	7	7	6

v[7].size가 2인 경우이다.

v[7] = 1, 2 이고 여기서 시작 위치의 값과 끝 위치의 값의 차가 K이하일 경우

끝 위치의 값과 쌍을 이루는 값들의 개수인 끝 위치 - 시작 위치를 카운트에 더해준다.

 

즉, 1, 2의 차가 K이하인 1이라서 (1, 2) 한 쌍을 카운트에 더해주는 것이다.

cnt = 1

 

등수	1	2	3	4	5	6
이름의 길이	7	7	6	7	7	6

 

v[7].size가 3인 경우이다.

v[7] = 1, 2, 4 이고 1, 4의 차가 K이하인 3이라서 (1, 4), (2, 4) 두 쌍을 카운트에 더해준다.

cnt = 1 + 2 = 3

 

등수	1	2	3	4	5	6
이름의 길이	7	7	6	7	7	6

 

v[7].size가 4인 경우이다.

v[7] = 1, 2, 4, 5 이고 1, 5의 차가 4로 K보다 큰 경우라서

시작 위치를 한 단계 뒤로 미룬다.

큐로 치면 pop을 해주는 것과 같다.

 

즉, v[7] = 1, 2, 4, 5 가 되고 2, 5의 차가 K이하인 3이라서 (2, 5), (4, 5) 두 쌍을 카운트에 더해준다.

cnt = 3 + 2 = 5

 

등수	1	2	3	4	5	6
이름의 길이	7	7	6	7	7	6

 

v[6].size가 2인 경우이다.

v[6] = 3, 6 이고 3, 6의 차가 K이하인 3이라서 (3, 6) 한 쌍을 카운트에 더해준다.

cnt = 5 + 1 = 6

 

이렇게 이 예시의 답은 6이 된다.

 

이대로 구현해주면 시간 초과의 고통은 끝

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector <int> v[21];
int start[21] = { 0 };

int main() {
	int N, K;
	cin >> N >> K;

	string name;
	long long cnt = 0;
	for (int n = 1; n <= N; n++) {
		cin >> name;
		int len = name.size();
		v[len].push_back(n); //이름의 길이의 인덱스에 등수 넣어줌

		if (v[len].size() >= 2) {
			while (1) {
				//이름의 길이가 같은 애들 중에서 등수의 차가 K를 넘을 때는 걸러줌
				if (v[len][v[len].size() - 1] - v[len][start[len]] > K) start[len]++;
				else {
					cnt += v[len].size() - 1 - start[len];
					break;
				}
			}
		}
	}

	cout << cnt;

	return 0;
}