백준 1083 소트

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

크기가 N인 배열이 있고, 최대 S번 연속한 두 개의 원소의 순서를 바꿀 수 있다.

소트 결과들 중 사전 순으로 가장 뒷서는 것을 출력하는 문제이다.

어떤 방법으로 접근할지 계획하기 위해 예제를 분석해 보았다.

배열이 [10, 20, 30, 40, 50, 60, 70]이 주어졌을 때, S의 값에 따른 결과는 다음과 같다.

S = 1일때, [20, 10, 30, 40, 50, 60, 70]
S = 2일때, [30, 10, 20, 40, 50, 60, 70]
S = 3일때, [40, 10, 20, 30, 50, 60, 70]

이를 보고 , 0번째 위치부터 현재 위치로 지정하고 S 범위 이내의 원소들 중 가장 큰 원소를 현재 위치로 옮겨온 뒤 현재 위치를 증가시키는 방법이 좋겠다 생각했다.

방법을 코드로 구현하기 위해 예시를 따라가보기로 하였다.

똑같이 [10, 20, 30, 40, 50, 60, 70]인데 S가 9인 경우로 해보자.

현재 위치를 ptr, 남은 교환 가능 횟수를 remain이라 하자. 그럼 위가 최초 상태이다.

현재 위치인 0에서부터, 최대 범위는 9이므로 배열 모든 원소까지 도달 가능하다.

따라서, 범위 내의 최댓값인 70을 현재 위치로 가져오고 현재 위치부터 가져온 70의 위치까지 한 칸씩 뒤로 민다.

70을 6칸 당겨왔으므로, remain을 6만큼 감소시키고 ptr을 1 증가시켜 다음 위치로 이동한다.

그럼 다음 위치에서의 상태는 위와 같다.

현재 위치인 1부터 remain(3)칸 이내의 범위인 색칠한 범위에서 가장 큰 값이 40이고, 이전 과정처럼 가져오고 당긴다.

그럼 위 상태처럼 40을 1번 위치로 옮기고, 10~30의 값은 가져온 만큼 뒤로 민다.
40을 3번 교환해 가져왔으므로 remain을 3 감소시킨다.

종료조건은 다음과 같다.
1. 모든 교환 가능 횟수(remain)를 사용해 0이 되었을 경우
2. 교환 가능 횟수(remain)는 남았지만 현재 위치(ptr)가 배열 끝까지 도달한 경우.

1번 종료조건에 해당하므로 [70, 40, 10, 20, 30, 50, 60]이 답이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val elements = readLine().split(' ').map{it.toInt()}.toTypedArray()
    val S = readLine().toInt()

    var remain = S
    var ptr = 0

    while(remain > 0 && ptr < elements.size){
        val ceil = if(ptr + remain >= elements.size) elements.size - 1
        		   else ptr + remain

        var max = elements[ptr]
        var maxIdx = ptr
        for(i in ptr..ceil){
            if(max < elements[i]){
                max = elements[i]
                maxIdx = i
            }
        }

        getDestValueAndPush(ptr, maxIdx, elements)
        remain -= maxIdx - ptr
        ptr++
    }

    val answer = StringBuilder()
    for(n in elements){
        answer.append("$n ")
    }
    print(answer.toString())
}

fun getDestValueAndPush(src: Int, dest: Int, elements: Array<Int>){
    if(src == dest) return

    val tmp = elements[dest]
    for(i in dest downTo src + 1){
        elements[i] = elements[i - 1]
    }
    elements[src] = tmp
}