[2023-05-23] 10973 이전 순열 (Kotlin)

 

문제 링크: https://www.acmicpc.net/problem/10973

10973번: 이전 순열

 

 

 

첫 번째 시도 (메모리 초과)

N과 M과 비슷한 유형이라 생각하여

 

바로 dfs로 풀어봤습니다.

 

 

package fiftysecond
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val input = br.readLine().split(' ').map{it.toInt()}

    val ansArr = Array(n){0}
    val visit = Array(n + 1){false}

    var prevArr = listOf<Int>()
    fun dfs(num: Int){
        if (num == n){
            var tag = true
            for (index in ansArr.indices){
                if (ansArr[index] != input[index])
                    tag = false
            }
            if (tag){
                if (prevArr.isEmpty())
                    println(-1)
                else{
                    prevArr.forEach{
                        print("$it ")
                    }
                }
                System.exit(0)
            }
            else
                prevArr = ansArr.toList()
            return
        }
        for (index in 1..n){
            if (!visit[index]){
                visit[index] = true
                ansArr[num] = index
                dfs(num+1)
                visit[index] = false
            }
        }
    }
    dfs(0)

}

 

 

구현이다 보니, 규칙을 찾아야 할 것 같았습니다.

 

규칙을 고민하는데에 50분 정도 걸린 것 같습니다.

 

 

두 번째 시도 (맞았습니다.)

 

// 맨 뒤에서 부터 내려오면서 연속 두 개의 원소를 비교
// 만약 앞서있는 원소가 더 작을 경우 
// 그 뒤에 있는 원소들 중, 앞서있는 원소보다 작으면서 가장 큰 원소를 찾고
// 앞서있는 원소 자리에 넣어줌
// 그 뒤에는 내림차순 정렬하여 출력


package fiftysecond
import java.io.*
import java.util.*

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val input = br.readLine().split(' ').map{it.toInt()}

    var last = input.last()
    val t = arrayListOf<Int>()
    var tag = true
    for (index in input.size - 2 downTo 0){
        if (last < input[index]){
            t.add(last)
            t.sort()
            for (i in 0 until index){
                print("${input[i]} ")
            }
            var value = 0
            for (i in t.size - 1 downTo 0){
                if (t[i] < input[index]){
                    value = t[i]
                    print("$value ")
                    break
                }
            }
            t.add(input[index])
            t.sort()
            for (i in t.size - 1 downTo 0){
                if (t[i] == value)
                    continue
                print("${t[i]} ")
            }

            tag = false
            break
        }
        else{
            t.add(last)
            last = input[index]
        }
    }

    if (tag)
        println(-1)


}