백준 3078. 좋은 친구

tose33 2023. 2. 11. 13:48

3078번: 좋은 친구

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

www.acmicpc.net

우선 이름의 길이가 다르면 절대 좋은 친구가 될수 없으므로, 벡터에 이름의 길이별로 등수를 저장한다.

이 벡터의 최대길이는 30만이 될수 있을 것이므로 그냥 2중 for문으로는 tle다.

30만 크기의 배열 mark를 만들어, mark[등수] = 이름이 같은 길이의 학생중 몇번째인지를 저장한다.

예를들어 등수가 다음과 같다면

aaa 1등

bbb 4등

ccc 6등

mark 배열은 아래와 같이 만들어진다.

K = 5 일때, aaa는 1등이고, 6등 까지는 aaa의 좋은 친구이다.

(mark[6] = 3) - (mark[1] = 1) = 2

따라서 aaa를 포함한 좋은친구 쌍은 2쌍이다.

큐로 푸는 방법.