백준 1039 교환 Kotlin

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

문제

---

생각하기

---

• 문자열을 K번 바꾸면서 최대값을 찾는 문제이다.

• BFS를 통해서 문자열을 바꾸고, 최적화를 위해 메모이제이션을 사용하면 풀 수 있다.

동작

결과

코드

---

Kotlin

BFS

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var K = 0
private lateinit var chArr: CharArray
private const val MAX = 1_000_001
private data class Swap(val num: String, val count: Int)

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(BFS())
    return sb.toString()
} // End of solve()

private fun BFS(): Int {
    val que = ArrayDeque<Swap>()
    val isVisited = Array(MAX) { BooleanArray(K + 1) }
    var ans = -1

    que.addLast(Swap(String(chArr), 0))


    while (que.isNotEmpty()) {
        val cur = que.removeFirst()

        if (cur.count == K) {
            ans = Math.max(ans, cur.num.toInt())
        }
        if (isVisited[cur.num.toInt()][cur.count]) continue
        isVisited[cur.num.toInt()][cur.count] = true

        for (i in 0 until N - 1) {
            for (j in i + 1 until N) {
                if (i == 0 && cur.num[j] == '0') continue
                if (cur.count + 1 > K) continue

                val swapNum = swap(cur.num, i, j)
                que.addLast(Swap(swapNum, cur.count + 1))
            }
        }
    }

    return ans
} // End of BFS()

private fun swap(str: String, i: Int, j: Int): String {
    val arr = str.toCharArray()
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

    return String(arr)
} // End of swap()

private fun input() {
    StringTokenizer(br.readLine()).run {
        chArr = nextToken().toCharArray()
        N = chArr.size
        K = nextToken().toInt()
    }
} // End of input()

DFS

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var K = 0
private var ans = 0
private lateinit var chArr: CharArray
private const val MAX = 1_000_001
private lateinit var memo: Array<BooleanArray>

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    DFS(String(chArr), 0)
    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun DFS(str: String, count: Int) {
    if (memo[str.toInt()][count]) return
    memo[str.toInt()][count] = true
    if (count == K) {
        ans = Math.max(ans, str.toInt())
        return
    }

    for (i in 0 until N - 1) {
        for (j in i + 1 until N) {
            if (i == 0 && str[j] == '0') continue

            val swapNum = swap(str, i, j)
            DFS(swapNum, count + 1)
        }
    }

} // End of DFS()

private fun swap(str: String, i: Int, j: Int): String {
    val arr = str.toCharArray()
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

    return String(arr)
} // End of swap()

private fun input() {
    StringTokenizer(br.readLine()).run {
        chArr = nextToken().toCharArray()
        N = chArr.size
        K = nextToken().toInt()
    }

    ans = -1
    memo = Array(MAX) { BooleanArray(K + 1) }
} // End of input()