[백준] 3078: 좋은 친구 - JAVA

https://www.acmicpc.net/problem/3078

 

풀이

학생의 이름이 등수 순으로 주어진다.

등수가 k를 넘지 않으면서 이름의 길이가 같으면 좋은 친구이다.

좋은 친구의 쌍을 구해야 한다.

처음에는 단순히 큐를 사용하면 되는 문제인 것 같았다.

하지만 메모리초과...

어떻게 푸는지 방법을 찾아보았다.

이름의 길이가 2~20이므로 길이 20의 큐 배열을 선언한다.

입력받은 문자열의 길이를 len이라고 한다면, 큐 배열의 len 인덱스에 들어있는 값이 해당 번호와 자신의 번호의 차가 k보다 크다면 poll 해준다.

poll 해준 뒤 남아있는 개수를 정답에 더해준다.

그 후 같은 인덱스에 자신의 등수를 넣어주면 된다.

 

---

 

메모리: 47332KB
시간: 368ms
언어: Java 11

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

public class Main {

    public static void main(String[] args) throws IOException {
        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());

        Queue<Integer>[] queues = new Queue[21];
        for (int i = 0; i < 21; i++) {
            queues[i] = new LinkedList<>();
        }

        long answer = 0;
        for (int i = 0; i < n; i++) {
            String name = br.readLine();
            int len = name.length();

            while (!queues[len].isEmpty() && queues[len].peek() < i - k) {
                queues[len].poll();
            }
            answer += queues[len].size();

            queues[len].add(i);
        }

        System.out.println(answer);
    }

}