백준 BOJ 3078 - 좋은 친구

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

3078번: 좋은 친구

등수의 차이가 $K$보다 작거나 같으면서 이름의 길이가 같은 친구들의 쌍 갯수를 세는 문제이다.

평범하게 생각하면 $O(N)$으로 훑어가면서 $O(2K)$에 등수의 차이가 작은 구간을 순회하게 되는데,

이 경우에는 $O(KN)$으로 TLE를 받아 제한시간 내에 문제를 해결할 수 없다.

 

투포인터를 활용한 스위핑으로 문제를 해결했다.

두개의 포인터 $l$ 과 $r$ 을 만드는데, 

 

현재 위치가 $N$ 일때 $l$ 은 $N-K$ 이고,

$r$ 은 $N+K$ 으로 정해서 구간을 정해줄 수 있다.

 

stdu라는 배열을 하나 만들어서

stdu[k]를 구간 $(l,r]$ 내에 있는 이름의 길이가 $K$ 인 학생들의 수 로 정해준다.

$l$이 커질때 l 위치에 있는 학생의 이름 길이 $len(S_l)$ 에 대하여

stdu[$len(S_l)$] -= 1이 되고, 동일한 방법으로

stdu[$len(S_r)$] += 1이 된다,

 

 

그러면 stdu[k] 를 통해서 좋은 친구들의 수를 구할 수 있는데,

주의할 점 세가지로

 

(l,r] 으로 정했으니 폐구간 개구간 신경써서 스위핑해줘야 하고,

 

stdu[k] 안에 자기 자신도 포함되기 때문에 1씩 빼서 사람수를 세줘야 하고,

 

A학생과 B학생이 서로 친한 친구라면

A-B 로 한쌍, B-A로 한쌍이 중복으로 세지기 때문에

출력할때 반으로 나눠서 출력해주어야 한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int stdu[25] = {0};
string arr[345678];

int main(){
	int N,K;
	cin >> N >> K;
	
	for(int i=1; i<=N; i++){
		cin >> arr[i];
	}
	
	int l,r;
	ll ans = 0;
	
	for(int i=1; i<1+K; i++){
		stdu[arr[i].length()]++;
	}
	
	for(int i=1; i<=N; i++){
		l = max(0,i-K-1);
		r = min(N+1,i+K);
		
		stdu[arr[r].length()]++;
		stdu[arr[l].length()]--;
		
		//printf("[%s %d]", arr[i].c_str(), stdu[arr[i].length()]);
		
		ans += stdu[arr[i].length()]-1;
	}
	
	cout << ans/2;
	return 0;
}

개인적으로 딱 재밌는 난이도 정도의 문제라서

푸는데 매우 흡족했다.