[백준]_3057 좋은친구

` queue 활용

K범위 내에 n명이 있다면 $_{n} \mathrm{C}_{2}$
- $_{n} \mathrm{C}_{2} = n(n-1) / 2 = 1 + 2 + … n-1 $
- 위에서 얻은 아이디어는 n번째 사람을 큐에 넣기 전에 n-1을 더하는 식을 생각
300000명의 이름의 길이가 모두 같을 경우를 생각해보면 int 범위를 넘어감.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


import java.io.*;
import java.util.*;

public class Main {
	static int n, k;
    static long cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        Queue<Integer> q[] = new LinkedList[21];
        for(int i=0;i<21;i++) {
        	q[i] = new LinkedList<>();
        }
        for (int i = 0; i < n; i++) {
        	int len = br.readLine().length();

    		while (!q[len].isEmpty() && i - q[len].peek() > k) {
    			q[len].poll();
    		}
    		
    		cnt += q[len].size();
    		q[len].offer(i);
		}
        System.out.println(cnt);
	}

}

[백준]_3057 좋은친구

See Also: