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

 

https://school.programmers.co.kr/learn/courses/30/lessons/138477?language=swift 

프로그래머스

 

처음엔 c++로 우선순위 큐로 할까 하고 했는데 뭐가 잘못되었는지 실패했다.

그래서 swift로 다시 차분하게 진행해봤다. 

honor에는 최대 k개의 점수가 들어가도록 한다. 내림차순으로 점수를 정렬하는데, 여기서 sort를 사용해도 될까?

swift의 sort는 O(nlogn)의 시간 복잡도를 가지고, 최대 k는 100으로 시간 복잡도에서는 괜찮을 거 같다.

 

1. honor 내 점수 개수가 k개보다 적다면, honor에 점수를 추가한다.

2. honor의 최소 점수보다 크다면 맨 뒤에 점수(최소 점수)를 빼고 해당 점수를 넣는다. 그 후, 내림차순으로 정렬

3. honor 내의 최소 점수를 answer에 넣는다.

 

import Foundation

func solution(_ k:Int, _ score:[Int]) -> [Int] {
    var answer = [Int]()
    var honor = [Int]()
    for sc in score {
        if honor.count < k {
            honor.append(sc)
        }
        if sc > honor.min()! {
            honor.removeLast()
            honor.append(sc)
            honor.sort(by: >)
        }
        answer.append(honor.last!)
    }
    return answer
}