[Kotlin] BOJ1039 교환

이런 유형도 DFS ,BFS로 풀 수 있구나 깨달았던 문제

다른 블로그 들을 참고하면서 DP와 BFS에 대해서 좀 더 깊게 깨달았구나 싶다.

 

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

1039번: 교환

 

해당 문제를 그리디로 머리 꽁꽁싸매고 열심히 풀어보았으나

1488 2 일 때,
8841 이 나오겠지만,
4188 2 일 때,
8814가 나옴으로
아래 그리디 방식으로는 풀 수 없다..
(다른 블로그도 그리디는 다 실패하신듯 하다..)

그 후 BFS와 DFS로 구현할 수 있다는 걸 알고 아래 블로그를 참고하고 풀었다.

(VIsited는 그냥 HashMap으로 해도 될거같아서 HashMap으로 사용했다.)

 

그리고 DFS를 구현할때 DFS에 반환값을 있게 구현하고 싶었는데

DP로 메모이제이션하기 위해서는 지나온 길을 기록을 해야하는데 반환값이 없다면

stack으로 혹은 다른 컬렉션으로 지나온 길을 저장하고

목적지에 도착했을때 DP에 기록하는형태로 구현을 해야하는데 시간복잡도 측면에서 낭비에 가깝다.

(이렇게 구현하니까 시간초과가 나왔다.)

 

결론 :

DP에 메모이제이션을 이용하려면 DFS에 반환값이 있는형태가 시간복잡도 측면에서 좋다.

 

이 문제는 DFS ,BFS 둘다 얼추 시간은 비슷하게 나오나 DP에 대해서 잘 몰랐던 사람으로써는

BFS가 좀 더 편하게 풀렸다. DP에 좀 더 익숙해지자! (퐈이팅)

 

#BFS 풀이

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.ArrayDeque
import kotlin.collections.HashMap

private lateinit var N :String
private lateinit var Q :ArrayDeque<Pair>
private lateinit var isVisited :HashMap<String,Boolean>
private var K = 0

private data class Pair(val num :String,
                        val count :Int)
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken()          //(백만이하 자연수)
    K = st.nextToken().toInt()  //10보다 작거나 같은 자연수
    Q = ArrayDeque<Pair>()
    isVisited = HashMap<String,Boolean>()
    var answer = -1

    //N이 한 자리수라면 바꿀 수 없음
    //N이 두 자리수고 뒤에가 0이라면 바꿀 수 없음
    if ((N.length == 1) || (N.length == 2 && N[1] == '0')){
        println(answer)
        return
    }

    //K번의 위치 교환을 수행한 수 중에 가장 큰 수를 구하는 문제
    var count = 0
    Q.add(Pair(N, count))
    while (Q.isNotEmpty()){
        //큐에서 꺼냄
        val pair = Q.removeFirst()

        //한 층에서 탐색을 다 끝냈다면 isVisited 초기화
        //(K번 이전에 답을 이미 방문했었을 수도 있음으로
        //isVisited는 매 회차의 탐색이 지났으면 초기화해준다.)
        if (count != pair.count) {
            isVisited = HashMap<String,Boolean>()
            count = pair.count
        }

        //목적지인가? -> count가 K인가?
        if (pair.count == K){
            val target = pair.num.toInt()
            answer = if(target > answer) target else answer
            continue
        }
        //연결된 곳 순회 -> 자리를 바꿀 수 있는 모든 경우의 수
        val length = pair.num.length
        for (i in 0 until length){
            for (t in i+1 until length){
                val newValue = swap(pair.num,i,t)
                //갈 수 있는가? ->  맨 앞자리가 0이 아니고, 방문하지 않은 수
                if((newValue[0] != '0') && (isVisited[newValue] == null)){
                    Q.add(Pair(newValue,pair.count +1))
                    isVisited[newValue] = true
                }
            }
        }
    }
    println(answer)
}
private fun swap (num :String, i :Int, t :Int) :String{
    val returnValue = StringBuilder(num)
    val temp = returnValue[i]
    returnValue[i] = num[t]
    returnValue[t] = temp

    return returnValue.toString()
}

#DFS풀이

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import java.util.*
private lateinit var N :String
private var K = 0
private lateinit var DP :HashMap<Point,Int> 
//코틀린은 equals override하지 않아도 default로 내용물이 같으면 같은 키로 인식함
var answer = -1

private data class Point(val num :String,
                        val count :Int)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken() //String  //(백만이하 자연수)
    K = st.nextToken().toInt()  //10보다 작거나 같은 자연수
    DP = HashMap<Point,Int>()

    //N이 한 자리수라면 바꿀 수 없음
    //N이 두 자리수고 뒤에가 0이라면 바꿀 수 없음
    if ((N.length == 1) || (N.length == 2 && N[1] == '0')){
        println(answer)
        return
    }
    println(dfs(N,0))
}
//DP에 메모이제이션을 이용하려면 DFS에 반환값이 있는형태가 시간복잡도 측면에서 좋다.
    //만약 반환값이 없다면 stack으로 혹은 다른 컬렉션으로 지나온 길을 저장하고
    //목적지에 도착했을때 DP에 기록하는형태로 구현을 해야하는데 시간복잡도 측면에서 낭비에 가깝다.


private fun dfs(num :String, count :Int) :Int{
    val currentPoint = Point(num,count)
    //저장된 값이 있는가?
    if(DP[currentPoint] != null){
        return DP[currentPoint]!!
    }

    //목적지인가? -> count가 K인가?
    if (count == K){
        val target = num.toInt()
        answer = if (target > answer) target else answer //answer 갱신
        return target
    }else{
        //연결된곳 순회 -> 자리를 바꿀 수 있는 모든 경우의 수
        val length = num.length
        for (i in 0 until length){
            for (t in i+1 until length){
                val newValue = swap(num,i,t)
                //갈 수 있는가? -> 맨 앞자리가 0이 아니고
                if (newValue[0] != '0'){
                    //간다.
                    val nextPoint = Point(newValue,count +1)
                    DP[nextPoint] = dfs(newValue,count +1)
                }
            }
        }
    }
    return answer
}

private fun swap (num :String, i :Int, t :Int) :String{
    val returnValue = StringBuilder(num)
    val temp = returnValue[i]
    returnValue[i] = num[t]
    returnValue[t] = temp

    return returnValue.toString()
}

 

#Greedy (실패)

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import java.util.StringTokenizer
private lateinit var N : CharArray
private lateinit var sortedN: List<Data>
private var K = 0
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toCharArray() //String  //(백만이하 자연수)
    K = st.nextToken().toInt()  //10보다 작거나 같은 자연수

/*
        1488 2 일 때,
        8841 이 나오겠지만,
        4188 2 일 때,
        8814가 나옴으로
        아래 그리디 방식으로는 풀 수 없다..
        (다른 블로그도 그리디는 다 실패하신듯 하다..)
*/

    //탐욕법 원칙
    // 현재 제일 앞에있는 수가 제일 큰 수인지 확인한다.
        // 제일 큰 수라면 그냥 둔다
        // 제일 큰 수가 아니라면
            // 제일 큰 수를 찾고 제일 앞에 세운다.(앞에 넘어온 수는 놔두고 그 다음 위치로)
                // 제일 큰 수가 두 개 이상이라면 뒤에 있는 놈을 뽑아서 제일 앞에 세운다. (큰 수가 최대한 앞에 있을 수록 숫자가 커짐으로)
                // 바꾸려고 하는 숫자가 0이고 가야하는 자리가 맨앞이라면 혹은 N이 한자리 숫자라면 -1을 출력한다.
            // 인덱스 끝까지 검사를 다 했는데 K가 남아있다면 맨 뒤에있는 숫자 두 개 위치를 바꾼다.
    val temp = N.clone().toCollection(ArrayList())
    val answer = ArrayList<Char>()

    //N이 한 자리수라면 바꿀 수 없음
    //N이 두 자리수고 뒤에가 0이라면 바꿀 수 없음
    if ((temp.size == 1) || (temp.size == 2 && temp[1] == '0')){
        println("-1")
        return
    }

    while (true){
        //K 체크
        if (K == 0) {
            if (N.size != answer.size){
                answer.addAll(temp)
            }
            break
        }

        // 인덱스 끝까지 검사를 다 했는데 K가 남아있다면 맨 뒤에있는 숫자 두 개 위치를 바꾼다.
        if((K != 0) && (temp.size == 0)){
            if (K % 2 == 0) break
            else {
                val t = answer[answer.lastIndex -1]
                answer[answer.lastIndex -1] = answer[answer.lastIndex]
                answer[answer.lastIndex] = t
            }
            break
        }

        //우선순위 1.숫자 큰 순, 2. 인덱스 큰 순
        sortedN = temp.mapIndexed { index, c -> Data(index,c) }.sortedWith(compareByDescending<Data> { it.value }.thenByDescending{ it.index }) //NlogN

        //현재 pivot에 있는 수가 제일 큰 수 인가?
        if(temp.first() == sortedN.first().value){
            // 제일 큰 수라면 그냥 둔다
            answer.add(temp.removeFirst())
            // 제일 큰 수가 아니라면
        }else{
            // 제일 큰 수를 찾고 제일 앞에 세운다.
            val t = temp[0]
            temp[0] = sortedN.first().value
            temp[sortedN.first().index] = t
            answer.add(temp.removeFirst())
            K--
        }
    }

    println(answer.joinToString(""))
}

data class Data(var index: Int, var value :Char)

 

#참고 블로그

(DFS : https://subbak2.com/m/8)

[BOJ 백준] 교환(1039) Java

(BFS : https://subin-programming.tistory.com/371?category=941951)

[백준_1039번] 교환