[BOJ] 1294 문자열 장식 - P3

TaeGN·2024년 9월 17일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

84/114

문제풀이

문자열을 사전순으로 정렬하고 하나씩 채워나간다.

주의사항

두 문자열을 비교할 때, minOf(o1.length, o2.length)까지의 문자가 모두 같은 경우에는 문자열의 길이가 큰 것을 우선한다.

소요시간

50분

package 백준.Platinum.P3.p4380_문자열장식

import java.util.PriorityQueue

data class Str(val s: String, val idx: Int = 0) : Comparable<Str> {
    fun first() = this[0]
    fun length() = s.length - idx
    fun hasNext() = idx + 1 < s.length
    operator fun get(i: Int) = s[i + idx]
    override fun compareTo(other: Str): Int {
        for (i in 0 until minOf(length(), other.length())) {
            if (this[i] == other[i]) continue
            return this[i].compareTo(other[i])
        }
        return -length().compareTo(other.length())
    }
}

fun main() {
    val N = readln().toInt()
    val pq = PriorityQueue<Str>()
    repeat(N) { pq.add(Str(readln())) }
    val sb = StringBuilder()
    while (pq.isNotEmpty()) {
        val str = pq.poll()
        sb.append(str.first())
        if (str.hasNext()) pq.add(str.copy(idx = str.idx + 1))
    }
    println(sb)
}