[LV.1] 실패율

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

실패율은 다음과 같이 정의한다.
스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
• 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
• 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

N	stages	result
5	[2, 1, 2, 6, 2, 4, 3, 3]	[3,4,2,1,5]
4	[4,4,4,4,4]	[4,1,2,3]

---

오답 풀이

처음에는 각 stage별 도달한 사람 수를 담은 배열과 도달했지만 아직 clear하지 못한 수를 담은 배열 2개를 구해서, dictionary로 각 stage 별 failure 수치를 구한 다음, max 순서대로 결과 배열에 넣으면 된다고 생각했다.

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    
    var approach = [Int]()
    var approachNotClear = [Int]()
    var dictFailure = [Int: Double]()
    var result = [Int]()

    for i in 0..<N {
        approach[i] = 0
        approachNotClear[i] = 0
    }
    
    for stage in stages {
        var i = 0
        while i < stage-1 {
            approach[i] += 1
            i += 1
        }
        if i <= N {
            approachNotClear[i] += 1
        } 
    }
    
    for i in 0..<N {
        dictFailure[i+1] = Double(approachNotClear[i])/Double(approach[i])
    }
    
    for i in 1...N {
        let maxValue = dictFailure.max { a, b in a.value < b.value }
        result.append(Int(maxValue!.key))
        dictFailure.removeValue(forKey: maxValue!.key)   
    }
    
    return result
}

signal: illegal instruction (core dumped)

dictionary도 dictionary지만 overflow 발생으로 초과했다.

---

모범 답안 1)

[lgvv98] 프로그래머스 LV1 실패율

tuple을 활용해서 stage와 failure 수치를 저장한다.

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
	var tuple = [(Int, Double)]()  //[스테이지: 실패율]
    var player = stages.count
    
    //각 stage
    for i in 1...N {
    	//현재 스테이지에 도달한 사람 수
        var current = 0
        for j in 0..<stages.count {
        	//주어진 stage와 해당 stage 일치
            if stages[j] == i {
               current += 1
            }
        }
        
        //player: 도달하고 clear한 사람 수
        player -= current
            
        var failure = Double(current) / Double(player)
        tuple.append((i, failure))
    }
    
    tuple = tuple.sorted(by: {$0.1 > $1.1 })
        
    return tuple.map{ $0.0 }
}

코드도 간단하고, 문제 해결 Okay
But, 시간 소요가 꽤 걸림 & 실패율 계산 정의와 일치하지 않는 오류도 존재함

---

모범 답안 2)

[dudu_iOS.log] Programmers: 실패율 - Swift

도달하고 clear한 배열을 매번 구하면 시간 초과가 날 수 있으므로, 누적합을 활용해서 구해준다.

e.g.) stage 4 clear: stage 3까지의 clear 합을 활용

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
	//clear: 도달 & clear
    var clear = Array(repeating: 0, count: N+2)
    //approachNotClear: 도달, but not clear
    var approachNotClear = Array(repeating: 0, count: N+2)
    
    //각 도달한 stage input을 받아 현재 도달한 stage 및 그 이전 clear stage에 추가
    for stage in stages {
        approachNotClear[stage] += 1
        clear[stage - 1] += 1
    }
    
    //도달한 stage의 이전 stage들의 clear를 누적합으로 구해줘야 함
    for i in stride(from: N, through: 0, by: -1) {
        clear[i] += clear[i+1]
    }
    
    //배열 2개를 zip을 활용해 sequence 쌍으로 만듬
    return zip(clear[1...], approachNotClear[1...]).enumerated().map { 
    	//failure 값 얻기
        (index: Int, value: (clear: Int, notClear: Int)) -> (Int, Double) in
            let total = value.clear + value.notClear
            //모두 clear
            if total == 0 {
                return (index+1, 0)
            //도달했지만 clear하지 못한 경우
            } else {
                return (index+1, Double(value.notClear) / Double(total))
            }
        //(N+2)번째는 제외하고, failure값 내림차순 정렬
        }.dropLast().sorted {
            if $0.1 == $1.1 {
                return $0.0 < $1.0
            } else {
                return $0.1 > $1.1
            }
        // 그 때의 stage값을 return
        }.map { $0.0 }
}

---

다시 볼 사항들

zip(::)
Creates a sequence of pairs built out of two underlying sequences.

let words = ["one", "two", "three", "four"]
let numbers = 1...4

for (word, number) in zip(words, numbers) {
    print("\(word): \(number)")
}
// Prints "one: 1"
// Prints "two: 2"
// Prints "three: 3"
// Prints "four: 4"

let naturalNumbers = 1...Int.max
let zipped = Array(zip(words, naturalNumbers))
// zipped == [("one", 1), ("two", 2), ("three", 3), ("four", 4)]

enumerated()
Returns a sequence of pairs (n, x), where n represents a consecutive integer starting at zero and x represents an element of the sequence.

for (n, c) in "Swift".enumerated() {
    print("\(n): '\(c)'")
}
// Prints "0: 'S'"
// Prints "1: 'w'"
// Prints "2: 'i'"
// Prints "3: 'f'"
// Prints "4: 't'"

dropLast(_:)
Returns a subsequence containing all but the specified number of final elements.

let numbers = [1, 2, 3, 4, 5]
print(numbers.dropLast(2))
// Prints "[1, 2, 3]"
print(numbers.dropLast(10))
// Prints "[]"