[kotlin] 백준 3078번 - 좋은 친구

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

3078번: 좋은 친구

백준 3078번 코틀린 풀이입니다.
문제의 풀이는 그리 어렵지는 않으나, 해당 풀이를 떠올릴때 까지 애를 많이 먹었습니다.
(큐 문제인지 알고 접근하였으나, 🥲큐를 사용해서 어떻게 풀지? 만 열심히 고민했네요.)

그리디 + 큐 자료구조를 이용한 문제입니다.

문제

첫쨋줄에 학생의 수와 k가 주어지고, 학생들이 차례로 주어집니다.

4 2
IVA
IVO
ANA
TOM

학생들은 등수대로 주어지고, 진정한 친구는 등수가 k보다 더 차이나지 않고 이름의 길이가 같아야 합니다.

진정한 친구의 쌍을 구하는 문제입니다.

풀이1(시간초과)

처음에 직관적으로 떠올린 완전 탐색의 풀이입니다.
O(n^2) 으로 단순히 학생들을 순환하며 기준 학생에서 뒤의 k명의 학생들을 확인했을때 시간초과가 됩니다.

또, 아래 코드에서는 눈치채지 못했지만, answer를 0으로 선언했을 경우, Int의 최대값(약 2,000,000,000)을 넘어가
((3 ≤ N ≤ 300,000, 1 ≤ K ≤ N)이며, K == N일경우 최대 90,000,000,000이기 때문) Long자료형을 사용하여야 합니다.

// 시간초과
fun solution() {
    val br = System.`in`.bufferedReader()
    val (n, k) = br.readLine().split(" ").map(String::toInt)
    val students = arrayOfNulls<String>(n).map { br.readLine() }
    var answer = 0;
    for (i in 0..n - k) {
        for (j in i + 1..i + k) {
            if (j >= n) continue
            if (students[i].length == students[j].length) {
                answer++;
            }
        }
    }
    print(answer)
}

풀이2

이름은 최대 20글자로, 이름길이 + 1개만큼 큐를 생성해 줍니다.

이름자체보단 등수와 이름의 길이가 중요합니다.
현재 타겟하는 학생과 친구가 될 수 없는경우 큐에서 제외해줍니다. 모두 제외된 경우, 큐 남은 사이즈가 수가 친구의 쌍이 됩니다.
이름의 길이에 해당하는 큐에 해당하는 등수를 넣습니다.

fun solution2() {
    val br = System.`in`.bufferedReader()
    val (n, k) = br.readLine().split(" ").map(String::toInt)

    var answer = 0L;
    val queues = Array<MutableList<Int>>(21) { mutableListOf() }

    for(i in 0 until n){
        val nameLength = br.readLine().length
        val queue = queues[nameLength]
        while (queue.isNotEmpty() && i - queue.first() > k) {
            queue.removeFirst()
        }
        answer += queue.size
        queue.add(i)
    }
    print(answer)
}