[ 백준 10812 ] - 바구니 순서 바꾸기 (Kotlin)

 

 

10812번: 바구니 순서 바꾸기

 

문제 이해 & 기본 개념

• 1 ~ N 까지의 원소가 있는 배열이 존재
• begin ~ end 구간에서 mid를 기준으로 앞뒤를 바꾸는 문제

---

중요 포인트

• 스왑을 이용하면 배열 하나로 풀 수 있다.

 

---

최종 풀이

• mid ~ end의 원소를 스왑을 통해 앞으로 가져올 예정
• 범위의 마지막 원소부터 시작해서 범위의 맨 앞으로 끌어다 놓는다.
• mid ~ end 사이의 원소를 begin까지 swap하는 방식으로 반복하면 됨
• 최악의 경우는 구간이 1 ~ N이고 mid가 1인 경우
  • O(N^2)의 시간이 걸린다.
  • 뒤쪽 원소부터 시작해서 맨 앞으로 놓는 방식이 아니라 mid부터 시작해서 앞에다 쌓는 방법으로 풀면 조금 더 줄일 수 있겠지만, 해당 문제에선 시간이 넉넉하므로 패스

주의할 점

• 주의할 점까지는 아니지만 채점 과정을 보니 테스트 케이스(입출력)가 많은 것 같다.
• BufferedReader와 BufferedWriter를 이용하면 수행 시간에서 많이 차이가 날 듯 하다.

---

소스 코드

fun main(){
    val (n, m) = readln().split(" ").map { it.toInt() }
    val array = Array(n){ it+1 }

    repeat(m){
        val (begin, end, mid) = readln().split(" ").map { it.toInt() }
        repeat(end-mid+1){
            for (i in end-1 downTo begin){
                array.swap(i,i-1)
            }
        }
    }
    array.forEach { print("$it ") }
    println()
}

fun Array<Int>.swap(n:Int, m:Int){
    val temp = this[n]
    this[n] = this[m]
    this[m] = temp
}