[문제 접근]
단순히 각 학생마다 그 학생 기준에서 ‘좋은 친구’를 찾기 위해 주어진 N명 학생들의 조건을 확인하면 시간복잡도가 O(N*N), 즉 9*1e10이 되므로 주어진 1초 안에는 해결하지 못한다는 결론이 나와야 한다.
그럼 어떻게 시간을 줄여야 하는지에 초점을 두고 문제를 다시 읽어보자. 이때 학생들이 성적순으로 주어졌다는 입력의 조건과, ‘좋은 친구’의 조건에 등수가 포함되어있다는 사실에 주목해서 읽어보면 입력조건을 활용하여 좋은 친구의 조건 중 하나인 등수를 쉽게 확인할 수 있는 방법이 있을 것이라고 추측해볼 수 있다.
[필요한 자료구조]
주어진 학생들을 성적순으로 본다고 가정했을 때, 한 학생 기준에서 등수 차이가 K 이하인 학생들을 살펴본 뒤 다음 학생 기준으로 다시 좋은 친구들의 범위를 살펴봤다고 해보자. 이때 마치 맨 앞에 있던 학생은 살펴보는 범위 내에서 사라지고 반대로 맨 뒤에 있는 학생은 이전 범위에 포함되어있지 않다가 다음 학생으로 넘어갔을 때 범위 내에 포함되는 모습을 살펴볼 수 있다. 이는 우리가 알고 있는 선형 자료구조 중에서도 큐(queue)와 매우 유사한 모습인 것을 알 수 있다.
큐의 특징: 제일 먼저 들어간 원소가 제일 먼저 나옴(선입선출), FIFO (First In First Out)ex) 식당 앞 줄서기, 정수기 옆 종이컵 디스펜서
이처럼 큐라는 선형 자료구조를 활용한다면 등수가 높은 사람은 앞쪽에, 낮은 사람은 뒤쪽에 배치될 것이다.
[추가 point]
학생들을 입력받을 때, 학생의 등수와 이름의 길이만을 사용하여 ‘좋은 친구’의 여부를 확인할 것이다. 그래서 입력 받은 이후에는 학생의 이름을 계속 들고 다닐 필요가 없다.
또한, ‘좋은 친구’의 조건으로 이름의 길이가 같아야 한다고 했으므로 학생들을 차례로 큐에 넣기 전에 학생들을 이름 길이를 기준으로 분류하여 같은 이름 길이를 가진 학생들끼리 같은 큐에 넣는 방식을 사용할 수 있다.
→ 이는 get_next_line 과제(bonus part)에서 각 fd마다 keep 정적 변수를 넣어주는 것과 유사한 형식이라고 생각해볼 수 있다. 이때 fd는 학생들의 이름 길이가 되고, keep은 해당 이름 길이를 가진 학생들을 성적순으로 나열해놓은 큐가 될 것이다.
[전체 코드]
#include <iostream>
#include <queue>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
int N,K;
ll res; // res 값의 범위 고려해줄것
queue<int> q[21];
int main() {
FASTIO;
cin >> N >> K;
for(int i=0; i<N; i++) {
string s; cin >> s;
int len = s.length();
while (!q[len].empty() && i-q[len].front()>K)
q[len].pop();
res += q[len].size();
q[len].push(i);
}
cout << res;
}
// queue의 특징상 (FIFO) 등수 높은 사람이 더 앞에 있음
// 이름 길이별로 사람들을 queue에 넣은 뒤,
// 입력값을 새로 받을 때마다 등수차가 K보다 큰 사람들은 모두 pop
// 남은 사람들의 수가 해당 입력값의 좋은 친구들 수(쌍의 수)임
C++
복사
