개요

백준 3078번: 좋은 친구

• 입력
  첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

• 출력
  첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.

접근방법

1. 그냥 벡터를 사용해서 1등부터 k번째 등수안에 자신과 이름 같은 친구있는지 찾으려했으나
   시간 복잡도가 O(N*N)이므로 문제의 끝범위인 30만이 들어왔을 때, 90억번의 연산을 하게되어서
   시간초과가 뜰것이다.

2. 모르겠어서 뒤져본 결과, 큐를 이용한 풀이를 발견했고 정말 생각도 못한 접근방법이라 놀라웠다.
   우선 2~20글자의 이름을 받아오므로 이름의 길이 갯수만큼의 큐를 생성 한다.
   (2~20글자이므로 queue<int>[21])

   이 큐에는 입력되는 글자의 index값이 들어간다

3. 글자를 입력받올 때마다 해당 글자길이의 큐의 front()값과 입력값의 인덱스의 차이를 체크한다.
   인덱스 차이가 K보다 크다면 인덱스차이가 K보다 작거나 같을때까지 큐의 front()를 pop해준다

		//해당 이름길이를 담당하는 큐가 비거나, 이번 인덱스와 front()의 인덱스 차이가 K보다 작거나 같을 때까지
		while (!q[nameLen].empty() && i - q[nameLen].front() > K) {
			//pop해준다
			q[nameLen].pop();
		}

4. pop과정이 끝났다면 큐안의 있는 원소들은 지금 큐에 push하려는 값과 쌍을 이루는 원소들이다.
   결국 남은 큐의 사이즈가 지금 넣으려는 원소와의 쌍의 갯수다.

		//pop과정이 끝났다면 큐안의 남은 원소들이 지금 넣으려는 이름과의 쌍이되는 원소들이므로 
		//q[nameLen].size는 결국 쌍의 갯수가 된다. 따라서 답에 더해준다.
		Ans += q[nameLen].size();
		//쌍 갯수를 더했으므로 이번 인덱스 푸시.
		q[nameLen].push(i);
	}

코드

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

using namespace std;
int N=0,K=0;
string name="";
//글자수에 맞춰서 큐를 생성
queue<int> q[21];

void input() {
	cin >> N >> K;
}


void solution() {
	//N과 K의 최대 범위가 30만이므로 답 변수인Ans 값에 21억이 넘는 값이 들어올 수 있다!
	long long nameLen = 0,Ans=0;
	
	for (int i = 0; i < N; i++) {
		cin >> name;
		//입력된 이름의 길이 저장.
		nameLen = name.length();
		//해당 이름길이를 담당하는 큐가 비거나, 이번 인덱스와 front()의 인덱스 차이가 K보다 작거나 같을 때까지
		while (!q[nameLen].empty() && i - q[nameLen].front() > K) {
			//pop해준다
			q[nameLen].pop();
		}
		//pop과정이 끝났다면 큐안의 남은 원소들이 지금 넣으려는 이름과의 쌍이되는 원소들이므로 q[nameLen].size는 결국 쌍의 갯수가 된다.
		//따라서 답에 더해준다.
		Ans += q[nameLen].size();
		//쌍 갯수를 더했으므로 이번 인덱스 푸시.
		q[nameLen].push(i);
	}

	cout << Ans;
}

int main() {
	input();
	solution();
}

문풀후생

큐의 방법을 보고난후에도 큐의 사이즈를 더하는 부분이 왜 중간에 저 부분에 들어가는지 이해가 안가서 많이 고민을 했다.
사이즈-1을 해줘야하는거아닌가 쌍이라면 이런 생각부터,
매번 값이 들어가기 전에 사이즈를 계속 더하는게 어떻게 답이되나 이생각까지 했다.

하지만 이해하고보니 이번에 큐에 푸시할 원소값과의 쌍을 이루는 원소들이 바로
큐에 남아있던 원소들이고, 해당 원소들의 갯수가 결국 쌍의 갯수라는 걸 이해했다.

또한 최대 범위가 30만이므로 Ans에 21억이 넘는 값이 들어올 수 있어서 long long자료형을 사용해야 한다.