[Swift 알고리즘] Programmers 실패율

이게 1단계라니.. 쓰다.. ㅠ

 

Level 1 2019 KAKAO BLIND RECRUITMENT

실패율

실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

스테이지의 개수 N은 1 이상 500 이하의 자연수
stages의 길이는 1 이상 200,000 이하
stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.

 

입출력 예시

print(solution(5, [2, 1, 2, 6, 2, 4, 3, 3])) //[3, 4, 2, 1, 5]
print(solution(4, [4,4,4,4,4])) //[4,1,2,3]

 

실패 - 5, 9, 22 시간초과 

처음에 스테이지별 실패율을 딕셔너리로 담았다가 순서가 없기 때문에 정렬을 두 번이나 해줘야 해서 

아예 처음부터 순서대로 이차원 배열에 담아주었다. 

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    //[스테이지, 실패율]을 담을 이차원 배열 생성
    var arr = [[Float]]()
    for i in 1...N {
        if !stages.contains(i) { arr.append([Float(i), 0.0]) }
        else {
            arr.append([Float(i), Float(stages.filter{ $0 == i }.count) / Float(stages.filter{ $0 >= i }.count)])
        }
    }
    //실패율로 정렬 후, 스테이지만 [Int]()로 반환
    return arr.sorted(by: { $0[1] > $1[1] }).map{ Int($0[0]) }
}

이렇게 하니까 보기에는 깔끔하고 간단해 보이지만 아무리 고쳐봐도 시간 초과가 난다는 것 ㅠㅠㅠ

 

테스트 케이스가 더 추가되었나보다. 

아무리 해도 테스트 케이스 5, 9, 22번에서 시간초과로 실패가 떠서 도대체 뭐가 잘못된건가 하면서 구글링 해봐도 

사람들이 풀었다고 올린 답안도 나랑 비슷하고 똑같이 시간초과가 나더라.

질문하기 참고해보니 for문 안에서 filter함수로 개수를 새어주면 시간복잡도가 너무 커지기 때문에, stages 갯수를 미리 세어준 다음 for문을 돌리라는 조언이 있었다.

filter 편하다고 좋아했는데 시간복잡도가 큰 친구였구나.. 

 

다른 부분 아무리 고쳐봐도 안되는데

filter 포기하고 도대체 for문 안쓰고 어떻게 stages 갯수를 미리 세어주지..?

for문 여러번 돌리는 게 filter 쓰는거보단 낫다는건가..? 

 

통과 답안

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    //[(스테이지, 실패율)] 저장하기 위한 튜플 배열
    var failRate = [(Int, Float)]()
    //전체 사용자 수
    var total: Float = Float(stages.count)
    //스테이지별 클리어하지 못한 사용자 수 저장하기 위한 배열 생성
    var nonClearArr = Array(repeating: 0, count: N+1)
    for i in stages {
        nonClearArr[i-1] += 1
    }
    for i in 1...N {
        //클리어하지 못한 사용자 없는 스테이지의 경우 (실패율 0)
        if nonClearArr[i-1] == 0 { failRate.append((i, 0.0)) }
        else {
            failRate.append((i, Float(nonClearArr[i-1]) / total))
            //전체 사용자 수에서 다음 스테이지 도달하지 못한 사용자 수 빼주기
            total = total - Float(nonClearArr[i-1])
        }
    }
    //실패율 기준으로 내림차순 정렬 후, 스테이지만 반환하기
    return failRate.sorted(by: { $0.1 > $1.1 }).map{ $0.0 }
}

스테이지 별 클리어하지 못한 사용자 수 미리 받아오는 건 타인의 코드를 참고해버렸다.. 

최소한의 반복문으로 단계별로 값을 구해가는게 포인트.. 

 

 

참고 : Swift 나누기, Float / Double