글 읽기 - heapSort 틀렸습니다.

skjh0818 2년 전 0

heapSort로 문제를 풀었는데 2%에서 계속 "틀렸습니다"가 출력이 됩니다.. 제가 어느부분을 실수한 것일까요?

import java.lang.StringBuilder

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = Array(n + 1) { 0 }
    val stringBuilder = StringBuilder()

    for (i in 1 until arr.size)
        arr[i] =br.readLine().toInt()

    for (i in arr.size / 2 -1  downTo 1) {
        heapfy(arr, i, arr.size)
    }

    for(i in 1 until arr.size){
        stringBuilder.append(remove(arr, i)).append("\n")
    }
    print(stringBuilder.toString())
    br.close()
}

fun remove(arr: Array<Int>, i: Int): Int {
    val head = arr[1]
    val size = arr.size - i

    arr[1] = arr[size]
    heapfy(arr, 1, size)
    return head
}

fun heapfy(arr: Array<Int>, parentIdx: Int, size: Int) {
    val lidx = getLeftIdx(parentIdx)
    val ridx = getRightIdx(parentIdx)
    var minIdx = parentIdx

    if (lidx < size && arr[lidx] < arr[minIdx])
        minIdx = lidx

    if (ridx < size && arr[ridx] < arr[minIdx])
        minIdx = ridx

    if (minIdx != parentIdx) {
        swqp(arr, minIdx, parentIdx)
        heapfy(arr, minIdx, size)
    }
}

fun swqp(arr: Array<Int>, idx1: Int, idx2: Int) {
    val temp = arr[idx1]
    arr[idx1] = arr[idx2]
    arr[idx2] = temp
}

fun getLeftIdx(idx: Int) = idx * 2

fun getRightIdx(idx: Int) = getLeftIdx(idx) + 1

skjh0818 2년 전 0

자답입니다. 배열값을 초기화 할때부터 검사를 진행했어야했는데 값을 다 넣고서 heapfy를 한 게 원인이었습니다.

이미 값이 들어있는 상태라면 지금처럼 풀면 됐을 것 같은데 하나하나 받은 후 처리하다보니 insert한 부분을 빼먹었네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

heapSort 틀렸습니다.

skjh0818 2년 전 0

skjh0818 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말