프로그래머스 - 기능 개발 (Queue 사용)

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

프로그래머스

 

 

아이디어

1. 뒤에 있는 기능은 앞에 있는 기능보다 먼저 개발되어도 앞에 있는 기능이 배포될 때 같이 배포된다
-> 앞 기능이 무조건 먼저 나간다 (FIFO) -> 큐 사용

2. periods: 각 작업이 완료될 때까지 필요한 기간을 나타내는 배열 
ex) 
progresses(작업 진도): [93, 30, 55]
speeds(작업 속도): [1, 30, 5]
periods(작업 완료까지의 기간): [7, 3, 9]

작업 완료까지의 기간을 수식으로 나타내면 아래와 같음

    100 <= progress + speed * x
    100 <= progress + speed * x
    100 - progress <= speed * x
    (100 - progress]) / speed <= x
    올림((100 - progress) / speed) = x
->  periods[i] = Int(ceil(Double(100 - progresses[i]) / Double(speeds[i])))

3. periods를 pop하면 처음 period가 나옴
- 이후 pop 하면서 처음 period보다 작거나 같으면 계속 Pop (count + 1) 
    - count: 같이 배포되는 기능의 개수
- 앞선 기능보다 오래걸리는 작업은 이전 작업 배포 이후에 배포됨
- 그렇다면, 앞선 기능보다 오래 걸리는 작업 기준으로 배포를 나누면 됨
- 이전 기능들의 개수를 배열에 저장하고 오래 걸리는 작업부터 다시 count
- queue가 비어질 때까지 반복

 

import Foundation

func solution(_ progresses:[Int], _ speeds:[Int]) -> [Int] {
    var periods = Array(repeating: 0, count: progresses.count)
    for i in progresses.indices {
        periods[i] = Int(ceil(Double(100 - progresses[i]) / Double(speeds[i]))) // ceil: 올림
    }
    
    var queue = Queue(periods)
    var firstPeriod = queue.dequeue()! // 앞 기능의 작업 기간
    var count = 1
    var answer = [Int]()
    
    while !queue.isEmpty {
        let num = queue.dequeue()!
        if firstPeriod >= num { 
            count += 1
            continue
        } else {
            answer.append(count)
            firstPeriod = num
            count = 1
        }
    }
    
    answer.append(count)
    return answer
}

struct Queue {
    private var inStack: [Int]
    private var outStack = [Int]()
    
    init(_ nums: [Int]) {
        inStack = nums
    }
    
    var isEmpty: Bool {
        inStack.isEmpty && outStack.isEmpty
    }
    
    mutating func enqueue(_ num: Int) {
        inStack.append(num)
    }
    
    mutating func dequeue() -> Int? {
        if outStack.isEmpty {
            outStack = inStack.reversed()
            inStack = []
        }
        
        return outStack.popLast()
    }
}