프로그래머스 / 명예의 전당 (1)

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

파이썬

힙큐를 이용하면 조금 빠르려나... 

def solution(k, score):
    import heapq
    answer, honer = [], []
    for each in score:
        heapq.heappush(honer, each)
        if len(honer) > k:
            heapq.heappop(honer)
        answer.append(honer[0])  # honer[0] = 가장 작은 원소
    return answer

테스트 1 〉	통과 (0.01ms, 10MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 9.97MB)
테스트 5 〉	통과 (0.02ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.02ms, 10.2MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.1MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)
테스트 12 〉	통과 (0.18ms, 10.2MB)
테스트 13 〉	통과 (0.18ms, 10.2MB)
테스트 14 〉	통과 (0.17ms, 10.3MB)
테스트 15 〉	통과 (0.68ms, 10.3MB)
테스트 16 〉	통과 (0.83ms, 10.4MB)
테스트 17 〉	통과 (0.36ms, 10.2MB)
테스트 18 〉	통과 (0.37ms, 10.4MB)
테스트 19 〉	통과 (0.27ms, 10.1MB)
테스트 20 〉	통과 (0.29ms, 10.2MB)
테스트 21 〉	통과 (0.54ms, 10.3MB)
테스트 22 〉	통과 (0.29ms, 10.4MB)
테스트 23 〉	통과 (0.53ms, 10.4MB)
테스트 24 〉	통과 (0.29ms, 10.3MB)
테스트 25 〉	통과 (0.60ms, 10.3MB)
테스트 26 〉	통과 (0.01ms, 10.1MB)

힙큐가 빠르군

def solution(k, score):
    answer, honer = [], []
    for each in score:
        honer.append(each)
        if len(honer) > k:
            honer.remove(min(honer))
        answer.append(min(honer))
    return answer

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.02ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10MB)
테스트 8 〉	통과 (0.02ms, 10.1MB)
테스트 9 〉	통과 (0.02ms, 10.1MB)
테스트 10 〉	통과 (0.03ms, 10.3MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (1.58ms, 10.3MB)
테스트 13 〉	통과 (1.64ms, 10.2MB)
테스트 14 〉	통과 (1.24ms, 10.2MB)
테스트 15 〉	통과 (3.62ms, 10.3MB)
테스트 16 〉	통과 (4.61ms, 10.2MB)
테스트 17 〉	통과 (3.68ms, 10.3MB)
테스트 18 〉	통과 (4.09ms, 10.2MB)
테스트 19 〉	통과 (0.54ms, 10.3MB)
테스트 20 〉	통과 (0.54ms, 10.3MB)
테스트 21 〉	통과 (0.64ms, 10.3MB)
테스트 22 〉	통과 (0.67ms, 10.3MB)
테스트 23 〉	통과 (0.69ms, 10.3MB)
테스트 24 〉	통과 (0.74ms, 10.4MB)
테스트 25 〉	통과 (0.77ms, 10.4MB)
테스트 26 〉	통과 (0.01ms, 10.2MB)

push와 pop을 별도로 하는 것 보다
pushpop을 쓰는 것이 더 빠르니... 

def solution(k, score):
    import heapq
    answer, honer = [], []
    for each in score:
        if len(honer) < k:
            heapq.heappush(honer, each)
        else:
            heapq.heappushpop(honer, each)
        answer.append(honer[0])  # honer[0] = 가장 작은 원소
    return answer

한 줄 더 늘어났지만.. 

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.05ms, 10.3MB)
테스트 8 〉	통과 (0.04ms, 10.2MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.02ms, 10.2MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)
테스트 12 〉	통과 (0.20ms, 10.2MB)
테스트 13 〉	통과 (0.11ms, 10.3MB)
테스트 14 〉	통과 (0.17ms, 10.3MB)
테스트 15 〉	통과 (0.25ms, 10.3MB)
테스트 16 〉	통과 (0.20ms, 10.4MB)
테스트 17 〉	통과 (0.40ms, 10.5MB)
테스트 18 〉	통과 (0.21ms, 10.2MB)
테스트 19 〉	통과 (0.16ms, 10.4MB)
테스트 20 〉	통과 (0.18ms, 10.3MB)
테스트 21 〉	통과 (0.20ms, 10.3MB)
테스트 22 〉	통과 (0.17ms, 10.4MB)
테스트 23 〉	통과 (0.17ms, 10.3MB)
테스트 24 〉	통과 (0.18ms, 10.3MB)
테스트 25 〉	통과 (0.17ms, 10.4MB)
테스트 26 〉	통과 (0.01ms, 10.1MB)

코틀린

import java.util.PriorityQueue

class Solution {
    fun solution(k: Int, score: IntArray): IntArray {
        val answer = mutableListOf<Int>()
        val honor = PriorityQueue<Int>()
        for (each in score) {
            if (honor.size < k) {
                honor.add(each)
            } else { // if (each > honor.peek()) 
                honor.add(each)
                honor.poll()
            }
            answer.add(honor.peek())
        }
        return answer.toIntArray()
    }
}

fun main() {
    println(
        Solution().solution(
            3, intArrayOf(10, 100, 20, 150, 1, 100, 200)
        ).contentToString()
    )
}