문제
N명의 학생이 성적순으로 나열되어 있다. 이름 길이가 같고 등수 차이가 K 이내인 학생 쌍을 "좋은 친구"라 할 때, 좋은 친구 쌍의 수를 구하라.
입력
첫째 줄에 학생 수 N (1 이상 300,000 이하)과 K (1 이상)가 주어진다. 이후 N줄에 성적순으로 학생 이름이 주어진다 (이름 길이 1~20).
출력
좋은 친구 쌍의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 2 ESAC TOOL KERO LACK | 3 |
풀이
이름 길이별 큐 배열을 사용하여 슬라이딩 윈도우 방식으로 좋은 친구 쌍을 센다.
- 이름 길이(1~20)별로 큐 배열을 준비한다
- 각 학생의 이름 길이 l에 대해, 큐 q(l)에서 등수 차이가 K를 초과하는 학생을 제거한다
- 큐에 남은 학생 수가 현재 학생과 좋은 친구인 쌍의 수이므로 답에 더한다
- 현재 학생을 큐에 추가한다
핵심 아이디어: 이름 길이가 같은 학생만 큐에 그룹핑하고, 등수 차이가 K를 초과하면 큐에서 제거하면 슬라이딩 윈도우 효과를 얻는다. 각 학생은 큐에 한 번 들어가고 한 번 나오므로 전체 O(N)에 처리된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day25BOJ3078좋은친구 { // 3078
static Queue<Integer>[] q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
long ans = 0;
q = new Queue[21];
for (int i = 0; i <= 20; i++) {
q[i] = new LinkedList<>();
}
for (int n = 0; n < N; n++) {
int l = br.readLine().length();
if (q[l].isEmpty()) {
q[l].offer(n);
continue;
}
while (n - q[l].peek() > K) {
q[l].poll();
if (q[l].isEmpty()) {
break;
}
}
ans += q[l].size();
q[l].offer(n);
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N) — 각 학생이 큐에 한 번 추가/제거 (amortized)
- 공간: O(N) — 큐 배열 전체 원소 수 합계