코딩테스트 연습 - 기능개발

문제 풀이 아이디어

작업이 완료가 되었다고 하더라도 앞에 작업이 완료가 되지 않으면 배포가 되지 않는 조건이 있습니다. 따라서 선입선출의 자료형인 Queue를 활용해서 풀어봅니다. 일반적인 array를 사용해도 문제는 풀리지만 array에서 element를 삭제할 때 시간복잡도는 O(N)입니다. 반면에 Queue에서 element를 삭제할 때는 O(1)입니다.

코드

import Foundation

// Swift로 큐 구현
struct Queue {
    private var index = 0
    var queue: [Int]
    
    init(_ queue: [Int]) {
        self.queue = queue
    }
    
    var count: Int {
        queue.count
    }
    
    var isEmpty: Bool {
        return queue.count == index
    }
    
    // 맨 처음 작업이 끝났는지 알아보기 위해 필요한 변수
        //❗️ index out of range를 조심!
    var first: Int {
        !self.isEmpty ? queue[index] : 0
    }
    
    // push 없이 pop만 구현해도 된다.
    mutating func pop() -> Int {
        defer {
            index += 1
        }
        return queue[index]
    }
}

func solution(_ progresses:[Int], _ speeds:[Int]) -> [Int] {
    
    var queue = Queue(progresses)
    var result = [Int]()
    
    while !queue.isEmpty {
        // 현재 작업 중에서 가장 첫번째 작업의 진행도가 100이 넘을 때까지 작업을 진행한다.
        while queue.first < 100 {
            for i in 0..<queue.count {
                queue.queue[i] += speeds[i]
            }
        }
        
        // 이번에 배포되는 작업을 세는 변수
        var count = 0
        
        // 앞에서부터 100이 넘은 작업들을 모두 배포한다.
        while queue.first >= 100 {
            _ = queue.pop()
            count += 1
        }
        
        // 이번에 배포된 작업들을 결과에 더한다.
        result.append(count)
        
    }
    
    return result
}

코드 다이어트

큐를 직접 구현해도 되지만 이번 문제는 push가 없으므로 그냥 index 변수를 하나 가지고 구현해도 별 문제 없습니다.

func solution(_ progresses:[Int], _ speeds:[Int]) -> [Int] {
    
    var queue = progresses
    var index = 0
    var result = [Int]()
    
    while index < queue.count {
        // 현재 작업 중에서 가장 첫번째 작업의 진행도가 100이 넘을 때까지 작업을 진행한다.
        while queue[index] < 100 {
            for i in index..<queue.count {
                queue[i] += speeds[i]
            }
        }
        
        // 이번에 배포되는 작업을 세는 변수
        var count = 0
        
        // 앞에서부터 100이 넘은 작업들을 모두 배포한다.
        while index < queue.count && queue[index] >= 100 {
            index += 1
            count += 1
        }
        
        // 이번에 배포된 작업들을 결과에 더한다.
        result.append(count)
        
    }
    
    return result
}