[프로그래머스] 실패율

programmers.co.kr/learn/courses/30/lessons/42889?language=swift

코딩테스트 연습 - 실패율

실패율 = 스테이지에 도달했으나 클리어 하지 못한 유저 수 / 스테이지 도달한 유저 수 

 

위 공식을 기반으로 실패율을 내림차순으로 정렬해주면 되는 문제이다. 

 

[프로그래머스] 실패율 (별 의미 없는 이미지..)

 

stages의 원소가 1이라면 1단계에 진입했으나 아직 클리어하지 못했다는 것을 의미한다. 

 

즉, n단계를 통과하지 못한 원소의 값은 n이 되는 것이다.  (도달은 해야하기에 n 미만은 포함 X)

바로 코드로 보면서 이해하는게 빠를 듯 하다. 

 

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {   
    // 단계별 클리어하지 못한 사용자 수를 저장하기 위한 배열 
    // N+1인 이유는 마지막 단계를 깬 사용자 수를 표시하기 위함 
    var nonClearArr = Array(repeating: 0, count: N+1)
    // (스테이지, 실패율) 저장용도
    var failRate = [(Int,Double)]()
    // 현재 단계까지 클리어하지 못한 사용자 수 (누적) 
    var nonClearUser = 0 
    // 전체 사용자 수
    let stageCnt = stages.count 
    
    // 배열에 단계별로 클리어하지 못한 인원 수 만큼 채워넣기
    for stage in stages {
        nonClearArr[stage-1] += 1
    }
    
    // 
    for i in 0..<N {   
        // 클리어하지 못한 사용자가 없을 경우 
        if nonClearArr[i] == 0 {
            failRate.append((i+1,0.0))
        } else { 
            failRate.append((i+1,(Double(nonClearArr[i]) / Double(stageCnt - nonClearUser))))
        }   
        // 클리어하지 못한 사용자 누적
        nonClearUser += nonClearArr[i]
    }        
    // 실패율이 같을 경우 stage가 빠른 순서대로 정렬해주고, 아닐 경우 실패율을 내림차순으로 하여 정렬해준다. 
    // map으로 stage만 뽑아내기 
    return failRate.sorted { if $0.0 == $1.0 { return $0.0 < $1.0} else {return $0.1 > $1.1}}.map {$0.0}
}

 

1단계 문제라고 해서 처음에 생각나는데로 풀었더니 5,9,22번이 시간 초과가 되면서 100점을 맞지 못했다. 

클리어하지 못한 사용자와 스테이지에 도달한 사용자 수를 모두 filter로 구했었다. 이 부분에 있어 stages의 길이가 200,000이고 N이 최대 500까지 가능하기에 시간 복잡도가 높았던 것 같다. 

 

위 처럼 최소한의 반복문으로 값을 구해나가는게 좋은 방법일 것 같다. 단계별로 진행되기에 최대한 이전의 값을 활용해주는게 포인트일 것 같다. 

 

[ 프로세스 ] 

1. 도달했으나 클리어하지 못한 사용자의 수, 도달한 사용자의 수를 각각 구한다. 

2. (스테이지, 실패율) 쌍으로 각각의 값을 구해 배열을 구성한다. 

3. 실패율 기준을로 내림차순 해주되, 실패율이 같을 경우 낮은 스테이지를 더 먼저 오도록 한다. 

 

포인트가 되는 부분은 반복문을 얼마나 최소화하는가, 그리고 정렬의 조건을 잘 따져주는 것 두 가지가 될 것 같다. 

---

1단계 문제를 이렇게 복잡하게 풀 줄은 생각도 못했다.... 시간 복잡도를 조금 더 고려해서 알고리즘을 구현하는 습관을 들여야할 것 같다. 

그러기 위해서는 너무 생각나는대로 바로 코딩하지 않고, 전체적인 흐름 / 구조를 보고 설계한 후 코드로 옮겨야겠다.