[백준]1517번 버블 소트

해당 문제의 주요 포인트는 병합정렬의 개념을 알고 있는지가 가장 중요한 문제였습니다.

병합정렬을 모른다고 하면 해당문제를 풀기는 매우 어려웠을 것으로 예상이 되며, 저도 아직 공부 부족이라 병합정렬에서 머리가 아팠던 문제 입니다.

머리가 아파 내용은 내일 추가 할 수 있도록 하겠습니다.

--------------------------------------------------------------------------내용 추가

※검색 시 코드가 나와있어도 코드는 대부분 보지 않고 개념만을 봤습니다.

해당문제를 처음 봤을 때 병합정렬이 아닌 다른 방식으로 접근했었습니다.

data class 를 만들어 놓고 안에 index값과 value 값을 넣어놓고 비교하는 형식으로 작성하였었으나, 해당 방식의 큰 문제 점은 swap의 횟수가 중복된다는 점이였습니다. 그 중복을 어떻게 체크하여 빼줄지 고민하였으나, 해답을 찾지 못하였고 다른 방식으로 풀어야 겠다는 생각이 들었고 아이디어 검색 및 방안을 찾다가 병합정렬을 사용하면 될 것 같다는 생각이 들었습니다.

근데 문제는 제가 병합정렬의 개념은 알고 있었으나 구현을 어떻게 해야 될지 감이 안잡혔었습니다. 그러다가 검색 중 재귀함수를 사용하면 된다는 힌트를 얻었습니다 그리고 생각해 보니 재귀 함수를 함수 내 상단부에서 실행을 하게 된다면 나눠 쪼개진 부위들이 먼저 실행이 되어 병합정렬의 개념과 일맥상통한다고 생각이 들었고 그 생각을 바탕으로 코드를 작성 하였습니다.

 

하기는 작성한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Long.compare
import java.util.*
import kotlin.Comparator

lateinit var arr : IntArray
lateinit var temp : IntArray
var result : Long = 0L

fun main() {
    //val s = System.currentTimeMillis()
    var br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt() // 자료의 개수
    //var sb = StringBuilder()
    arr = IntArray(N+1)
    temp = IntArray(N+1)
    st = StringTokenizer(br.readLine())
    repeat(N){
        arr[it+1] = st.nextToken().toInt()
    }
    Swap(1,N)

    print(result)

//    bw.flush()
//    bw.close()
//
//   val e = System.currentTimeMillis()
//   println((e-s)/1000.0)

}

fun Swap(s: Int, e: Int){
    if(e-s < 1)return
    var mid = s + (e-s)/2

    Swap(s,mid)
    Swap(mid+1,e)

    for(i in s .. e){
        temp[i] = arr[i]
    }

    var index1 = s
    var index2 = mid + 1
    var check = s

    while(index1 <= mid && index2 <= e){
        if(temp[index1] > temp[index2]){
            arr[check] = temp[index2]
            result += (index2-check)
            index2++
            check++
        } else {
            arr[check] = temp[index1]
            index1++
            check++
        }
    }
    while(index1 <= mid){
        arr[check] = temp[index1]
        index1++
        check++
    }
    while(index2 <= e){
        arr[check] = temp[index2]
        check++
        index2++
    }


}