[백준] 3078. 좋은 친구 (Kotlin)

문제

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

3078번: 좋은 친구

0. 문제 해석

1. 인덱스 0부터 시작점으로 하여 최대 k 만큼의 학생들과 이름의 길이를 비교해가며 길이가 같을경우를 세준다.
2. 시작점을 하나씩 늘려가며 마지막 인덱스가 시작점이 될 때 까지 반복한다.

 

위와 같이 완전탐색으로 진행한다면, 구현 자체는 어렵지 않다.

하지만 학생 수가 최대 300000 이므로 일반적인 반복으로 탐색하면 시간초과가 발생한다.

 

풀이 1 (오답)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val st = StringTokenizer(readLine())
    val n = st.nextToken().toInt() // 학생 수
    val k = st.nextToken().toInt() // 등수 차이
    val arr = arrayListOf<String>() // 이름 정보
    var count = 0 // 좋은 친구쌍 수

    // 정보 입력
    for(i in 0 until n){
        arr.add(readLine())
    }

    for(i in 0 until n){
        val len = arr[i].length
        for(j in (i + 1) .. (i + k)){
            // null check
            if(j >= n){
                break
            }

            // 이름의 길이가 같으면 좋은 친구
            if(arr[j].length == len){
                count++
            }
        }
    }
    println(count)
}

위에서 서술한대로 경우의 수를 전부 탐색하면 시간초과가 발생한다.

 

 

풀이 2 (정답)

// [백준] 3078. 좋은 친구 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val st = StringTokenizer(readLine())
    val n = st.nextToken().toInt() // 학생 수
    val k = st.nextToken().toInt() // 등수 차이
    val queue = Array<Queue<Int>>(21) { LinkedList<Int>() } // 길이별로 큐 생성
    var count = 0L // 좋은 친구쌍 수

    // 정보 입력
    for(i in 0 until n){
        val len = readLine().length

        while(queue[len].isNotEmpty()){
            // 범위를 벗어나는 값 poll
            if(i - queue[len].peek()!! > k){
                queue[len].poll()
            }
            else{
                break
            }
        }
        count += queue[len].size // 남은 값(범위에 속한 값)이 친구쌍 수이므로 더해줌
        queue[len].offer(i) // 현재길이 큐에 현재 인덱스 삽입
    }
    println(count)
}

 

1. 길이별로 (2~20) 정보를 저장하기 위한 큐를 각각 생성해준다.
2. 입력이 들어올 때 마다 그 입력 길이의 큐에 속한 원소들과 순서쌍을 이룰 수 있는지(범위를 벗어나는지) 확인한다.
3. 범위에 벗어나는 값들은 전부 큐에서 빼내고, 남은 값들의 수를 누적한다.
4. 현재 인덱스를 그 입력 길이의 큐에 삽입한다.

 

큐를 활용해 위 과정을 반복함으로써 시간을 크게 줄일 수 있다.