[프로그래머스] 실패율

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

프로그래머스

 

접근

---

• 실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
  → stages에서 스테이지별로 도전 중인 플레이어 수와, 스테이지에 도달한 플레이어 수를 카운팅해야 한다

 

(Int, Int) 튜플을 타입으로 받는 배열을 생성하여 (도전 중인 플레이어 수, 도달한 플레이어 수)를 카운팅한다. 이때 각 사용자가 도착한 모든 스테이지를 반복문으로 돌려서 카운팅을 해줄 경우, 200,000*500 = 1억이므로 시간초과가 발생할 수 있다. 이를 방지하기 위해 3번 스테이지에 도착한 사용자는 1번과 2번 스테이지에도 도착함을 의미하므로 dp를 활용할 수 있다. 스테이지가 3번까지 있다고 가정할 때, (3번에서 도전 중인 사용자 + 2번에서 도전 중인 사용자)는 2번에 도달한 사용자 수가 된다. 

 

코드

---

func solution(_ n:Int, _ stages:[Int]) -> [Int] {
    
    var count = [(Int, Int)](repeating: (0,0), count: n+1) //스테이지 도달했지만 클리어X 플레이어수, 스테이지에 도달한 플레이어수
    for s in stages {
        count[s-1].0 += 1
    }

    count[n].1 = count[n].0
    for i in stride(from: n-1, to: -1, by: -1){
        count[i].1 = count[i+1].1 + count[i].0
    }
    count.removeLast()

    return count.map{ Float($0)/Float($1) }.enumerated().sorted(by: { $0.1 > $1.1 }).map{ $0.0+1 }
}