hio9_9
또바기잇
hio9_9

블로그 메뉴

  • 홈
  • Github
  • Tistory
  • All (57)
    • 코딩테스트 연습 (28)
    • CS (13)
      • 알고리즘 (4)
      • 자료구조 (2)
      • 운영체제 (7)
    • 42 (9)
    • iOS (2)
    • GIT (3)
    • TIL (2)
hELLO · Designed By 정상우.
hio9_9

또바기잇

코딩테스트 연습

[BOJ] 3078. 좋은 친구 (data_structures, queue, sliding_window)

2023. 1. 9. 00:50

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 차이나는 학생 쌍의 개수 찾기
    1. 투 포인터로 학생들의 등수 차이를 모두 확인 → N, K ≤ 300,000 이므로 시간초과
    2. 누적합을 이용

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

    티스토리툴바