[BOJ] 3043 장난감 탱크 - P4

TaeGN·2024년 9월 18일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

85/114

문제풀이

행이 작은 순서로 정렬한 값들을 1 ~ N행에 배정하고, 열이 작은 순서로 정렬한 값들을 1 ~ N열에 배정하면 된다.
경로를 구할 때는 위로 올라가는 탱크는 행이 작은 탱크가 우선이고, 아래로 내려가는 탱크는 행이 큰 탱크가 우선이다. 왼쪽으로 이동하는 탱크는 열이 작은 탱크가 우선이고, 오른쪽으로 이동하는 탱크는 열이 큰 탱크가 우선이다.

주의사항

두 탱크가 동시에 같은 정사각형 안에 있을 수는 없다.

소요시간

40분

package 백준.Platinum.P4.p3043_장난감탱크

import kotlin.math.abs

fun main() {
    val N = readln().toInt()
    val rArr = IntArray(N)
    val cArr = IntArray(N)
    repeat(N) { idx -> readln().split(" ").map(String::toInt).let { rArr[idx] = it[0] - 1; cArr[idx] = it[1] - 1 } }
    var totalCount = 0
    val uList = mutableListOf<Pair<Int, Int>>()
    val dList = mutableListOf<Pair<Int, Int>>()
    val lList = mutableListOf<Pair<Int, Int>>()
    val rList = mutableListOf<Pair<Int, Int>>()
    val sortedRArr = rArr.asSequence().mapIndexed { index, i -> index to i }.sortedBy { it.second }.toList()
    val sortedCArr = cArr.asSequence().mapIndexed { index, i -> index to i }.sortedBy { it.second }.toList()
    for (i in 0 until N) {
        if (sortedRArr[i].second > i) uList.add(sortedRArr[i].first to abs(sortedRArr[i].second - i))
        else if (sortedRArr[i].second < i) dList.add(sortedRArr[i].first to abs(sortedRArr[i].second - i))
        if (sortedCArr[i].second > i) lList.add(sortedCArr[i].first to abs(sortedCArr[i].second - i))
        else if (sortedCArr[i].second < i) rList.add(sortedCArr[i].first to abs(sortedCArr[i].second - i))
        totalCount += abs(sortedRArr[i].second - i) + abs(sortedCArr[i].second - i)
    }
    val sb = StringBuilder()
    uList.asSequence().sortedBy { rArr[it.first] }.forEach { (idx, count) -> repeat(count) { sb.appendLine("${idx + 1} U") } }
    dList.asSequence().sortedBy { -rArr[it.first] }.forEach { (idx, count) -> repeat(count) { sb.appendLine("${idx + 1} D") } }
    lList.asSequence().sortedBy { cArr[it.first] }.forEach { (idx, count) -> repeat(count) { sb.appendLine("${idx + 1} L") } }
    rList.asSequence().sortedBy { -cArr[it.first] }.forEach { (idx, count) -> repeat(count) { sb.appendLine("${idx + 1} R") } }
    println(totalCount)
    println(sb)
}