Gold IV
https://www.acmicpc.net/problem/3078
3078번: 좋은 친구
첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.
www.acmicpc.net
상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.
- 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
- ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
- 상근: 근데?
- ??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
- 상근: 아? 근데 K는 어떻게 구해?
- ??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
- 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!
상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.
input:
- 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N)
- 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.
output:
- 첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.
Idea :
- 성적 순으로 N명의 학생 이름이 주어졌을 때, 등수가 k만큼 차이나고 이름의 길이가 같은 친구가 몇 쌍인지 구하는 문제
- 성적 순으로 이름이 주어지므로 현재 등수에서 ± k 까지는 모두 좋은 친구가 될 수 있음
- 그 중 이름의 길이가 같아야 함
- 이름의 길이를 기준으로 학생들을 나누고
- 이름의 길이가 같은 학생 리스트 내에서 등수가 k 차이나는 학생 쌍의 개수 찾기
- 투 포인터로 학생들의 등수 차이를 모두 확인 → N, K ≤ 300,000 이므로 시간초과
- 누적합을 이용
Code :
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("input.txt", "rt", stdin);
int N, K;
string name;
vector<int> list[21]; // 이름 길이에 따라 나눈 학생 리스트, list[i] = 이름의 길이가 i인 학생들의 등수
/* input & init */
cin >> N >> K;
for (int i=1; i<=N; i++) {
cin >> name;
list[name.length()].push_back(i); // 주어진 이름의 길이에 해당하는 배열에 현재 등수 추가
}
/* solve */
long long ans = 0;
for (int i=2; i<=20; i++) {
if (list[i].size()) {
vector<long long> sum(list[i].back()+1, 0); // 누적합 배열
for (auto e : list[i]) sum[e] = 1; // 현재 리스트에 포함되어 있는 등수를 1로 체크
for (int j=1; j<=list[i].back(); j++) {
// 현재 리스트에 포함된 등수일 경우
// j-k ~ j-1 사이에 있는 학생의 수 = 현재 등수의 학생과 좋은 친구가 되는 학생의 수
if (sum[j])
ans += (j > K) ? sum[j-1] - sum[j-K-1] : sum[j-1];
sum[j] += sum[j-1];
}
}
}
cout << ans << "\n";
}
Result :
메모리: 6308 KB, 시간: 52 ms
Review :
'코딩테스트 연습' 카테고리의 다른 글
[BOJ] 10799. 쇠막대기 (data_structures, stack) (0) | 2023.01.10 |
---|---|
[BOJ] 9020. 골드바흐의 추측 (math, number_theory, primality_test, 에라토스테네스의 체) (0) | 2023.01.10 |
[BOJ] 3980. 선발 명단 (backtracking, bruteforcing) (0) | 2023.01.09 |
[BOJ] 2505. 떡 먹는 호랑이 (bruteforcing, dp, math) (0) | 2023.01.08 |
[BOJ] 2661. 좋은 수열 (backtracking) (0) | 2023.01.04 |