프로그래머스 시간 측정 오류와 H-Index 문제

프로그래머스 Kotlin 시간 측정 오류

https://dodobest.tistory.com/86

Kotlin Boxing Type 쓰지 마세요 체질이라는게바뀝니다

 

예전에 Kotlin Boxing Type을 사용하거나, Kotlin Navtive 함수를 사용하면 코테 시간이 오래 걸려서 Boxing Type과 Kotlin Native 함수 사용을 지양해야 한다고 생각했다.

 

오늘 풀었던 H-Index도 IntArray의 sort 대신 Java의 Arrays.sort 함수를 이용해서 시간은 10ms에서 0.5ms로 단축시켰다. 하지만 내부 코드를 들여보면, 결국 호출하는 함수가 같다. 그래서 정말 차이가 존재하는지 직접 코드로 확인해봤다.

 

import java.util.*
import kotlin.random.Random

val random = Random(System.currentTimeMillis())

fun main() {
    val a = IntArray(100_000_000) { it }
    a.shuffle(random)

    val st = System.currentTimeMillis()
//    a.sort() // 6010, 6104, 6036
    Arrays.sort(a) // 6124, 6092, 6127
    val et = System.currentTimeMillis() - st

    println(et)
}

 

결과는 차이가 없다. 그럼에도 프로그래머스에서 시간 측정에 차이가 존재하는 이유는 Java 함수를 사용할 때 Kotlin에 맞도록 시간을 치환하지 않고 그대로 반영하는 것이 원인이라고 생각한다. 리트코드에서도 Java 코드는 시간 측정 단위가 1~10 단위라면 Kotlin은 100~900단위다.

 

따라서 프로그래머스에서 제출한 답안의 시간을 단축하기 위해 노력하기 보다는 단순히 맞으면 넘어가는 것을 추천한다.

제출한 코드가 얼마나 효율적인지 알아보고 싶다면 Leetcode를 추천한다.

https://leetcode.com/

 

 

H-Index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

 

IntArray를 이용해서 각 논문의 인용횟수를 기록했다. 과학자가 발표한 논문 횟수는 최대 1000편이므로, 인용 횟수가 1000편을 넘어가는 것은 1000편 인용된 것으로 카운트했다.

이후 count를 뒤에서부터 순차적으로 탐색하며, index보다 더 많이 인용된 논문이 존재하는지 확인했다.

class Solution {
    fun solution(citations: IntArray): Int {
        val count = IntArray(1001) // 1000번 초과는 1000로 기록
        for (citation in citations) {
            if (citation > 1000) {
                count[1000]++
            } else {
                count[citation]++
            }
        }
        var sum = 0
        for (idx in count.lastIndex downTo 0) {
            sum += count[idx]
            if (sum >= idx) {
                return idx
            }
        }
        return 0
    }
}

 

 

 

더 빠른 답안이 있는지 찾아보다가, 정렬을 이용한 방법을 발견했다. 일일이 인용 논문횟수를 기록하지 않고, 주어진 논문횟수 IntArray를 정렬한다. 가능한 최대 인용 횟수는 citations의 size라는 것을 이용해서 정렬된 IntArray를 순차적으로 탐색한다.

 

class Solution {
    fun solution(citations: IntArray): Int {
        citations.sort()
        val length = citations.size

        for (i in citations.indices) {
            if (citations[i] >= length - i) {
                return length - i
            }
        }
        return 0
    }
}

 

 

https://velog.io/@soorim_yoon/정렬-H-Index-프로그래머스-Level

[정렬] H-Index (프로그래머스, Level 2)

 

 

앞에서 프로그래머스 시간 측정 오류인 것을 확인했으나, Java의 Arrays.sort 를 이용하면 시간을 더 단축할 수 있기는 하다.

import java.util.*

class Solution {
    fun solution(citations: IntArray): Int {
        Arrays.sort(citations)
        val length = citations.size

        for (i in citations.indices) {
            if (citations[i] >= length - i) {
                return length - i
            }
        }
        return 0
    }
}