[Swift 알고리즘] Programmers 기능개발

○△

Level 2 스택/큐

기능개발

문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다.예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예시

print(solution([93,30,55], [1,30,5])) //[2,1]
print(solution([95,90,99,99,80,99], [1,1,1,1,1,1])) //[1,3,2]
print(solution([40, 93, 30, 55, 60, 65], [60, 1, 30, 5 , 10, 7])) //[1,2,3]
print(solution([93, 30, 55, 60, 40, 65], [1, 30, 5 , 10, 60, 7])) //[2,4]

내 답안

func solution(_ progresses:[Int], _ speeds:[Int]) -> [Int] {
    var daysArr = [Int]()
    for i in 0..<progresses.count {
        var days = (100 - progresses[i]) / speeds[i]
        if (100 - progresses[i]) % speeds[i] > 0 {
            days += 1
        }
        daysArr.append(days)
    }
    
    var result = [1]
    for i in 1..<daysArr.count {
        if daysArr[i] > daysArr[i-1] {
            result.append(1)
        } else {
            daysArr[i] = daysArr[i-1]
            result[result.count - 1] += 1
        }
    }
    return result
}

스택/큐 문제라고 했지만 그냥 구하고 더해서 풀어따,,

daysArr : 작업 완료 소요 일수 배열

days : 작업 완료 소요일 계산 시 / 를 이용하여 나눈 값에 소수점이 있을 시 하루를 더해주어 올림값을 구해준다. 

결과값을 [1] 로 먼저 선언해준 후, days배열에서 앞 순서 일수가 뒷 순서 일수보다 클 경우 해당 인덱스에 +1 해주고 앞 순서 일수 값을 뒷 순서 값에 덮어씌운다.

뒷 순서 일수가 앞 선수 일수보다 클 경우 결과값 배열에 1을 append 해준다. 

이렇게 하여 결과 배열을 구해준다. 

 

 

다른 풀이

func solution(_ progresses:[Int], _ speeds:[Int]) -> [Int] {
    var daysArr = [Int]()
    var result = [Int]()
    for i in progresses.indices {
        daysArr.append((100 - progresses[i] - 1) / speeds[i] + 1)
    }
    while !daysArr.isEmpty {
        let longestTask = daysArr.first!
        var taskCnt = 0
        while !daysArr.isEmpty && daysArr.first! <= longestTask {
            taskCnt += 1
            daysArr.removeFirst()
        }
        result.append(taskCnt)
    }
    return result
}

for 문을 돌릴 때, 0..<progresses.count 대신 progresses.indices 를 사용할 수도 있다. 딱히 시간은 별 차이 없다. 

올림 값을 구해줄 때 따로 나머지를 구해주지 않아도, (100 - 초기개발% - 1) / 개발속도 + 1 을 해주면 된다. 

* 분자에 -1을 하고 나누기 연산 후 +1을 해주면 Int 타입의 연산이 결과값을 내림처리 하는 것을 방지할 수 있다.  

for문 대신 while을 이용해 반복문을 돌려주어 배열의 첫번째 항목을 removeFirst() 를 사용해 지워나가는 방법이다.

그런데 removeFirst() 연산은 큐의 pop()과 달리 O(N)의 복잡도를 가져, 위 알고리즘의 시간 복잡도는 O(N^2)가 된다고 한다. 

단순 배열 큐를 사용할 때 removeFirst() 메서드 사용을 지양하는 편이 더 나을수도?

따라서 다음과 같이 배열큐와 커서를 사용하여 O(N) 시간복잡도로 푸는 것이 더 효율적. 

func solution(_ progresses:[Int], _ speeds:[Int]) -> [Int] {
    var daysArr = [Int]()
    var result = [Int]()
    for i in progresses.indices {
        daysArr.append((100 - progresses[i] - 1) / speeds[i] + 1)
    }
    var index = 0
    while index < daysArr.count {
        let longestTask = daysArr[index]
        var taskCnt = 0
        while index < daysArr.count && daysArr[index] <= longestTask {
            taskCnt += 1
            index += 1
        }
        result.append(taskCnt)
    }
    return result
}

위와같이 커서를 사용하면 내 코드랑 크게 차이는 없는 듯