기능개발

🔒문제

---

💭 생각의 흐름

(1) 진도율이 100% 될 때 까지 선행작업(맨 첫번 째 작업)에 필요한 일수를 구한다.
(2) 후행작업 진도 + 선행작업에 소요된 일수 * speed >= 100 ? 다음놈 검사 : break!

---

🔑 풀이

const val COMPLETE_PERCENT = 100
const val NOT_FOUND = -1

class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        var answerList = ArrayList<Int>()
        var day = 0
        var index = 0
        
        while (index < progresses.size) {
            while (true) if (progresses[index] + (++day * speeds[index]) >= COMPLETE_PERCENT) break
//          indexOf 함수이면서 range 정할 수 있는 함수가 있었으면 좋겠다.. js나 python 처럼
            var nextIndex = -1
            for (startIndex in index + 1 until progresses.size) { // (2) range search
                if (progresses[startIndex] + day * speeds[startIndex] < COMPLETE_PERCENT) {
                    nextIndex = startIndex
                    break
                }
            }
            
            // 뒤에 더 이상 완료되지 않은 작업이 없음
            if (nextIndex == NOT_FOUND) {
                answerList.add(progresses.size - index)
                break
            } else {
                answerList.add(nextIndex - index)
                index = nextIndex
            }
        }
        return answerList.toIntArray()
    }
}

---

🔑 풀이 2

풀이 1은 최악의 시간복잡도는 O(N^2)이다.
progresses = [99, 98, .....2, 1]
speeds = [1, 1, 1, ....1] 일 경우 1부터 98까지의 합 즉 98 * 97 / 2
약 N^2 / 2 가 소요된다..

반면 이 풀이2는

(1) progresses를 모두 남은 일수로 대치하여 소요시간 선후관계를 미리 정의하고
(2) 무조건 선행 기능의 '남은 일수'를 기준으로 대소관계를 비교하여 배포 갯수를 따진다.
총 2번의 loop으로 O(N) 약 2N의 시간 복잡도를 갖는다.

⭐ loop 를 돌때 주의사항 ⭐

• 초기화
• 맨 첫자리와 마지막자리 처리
• outOfBound 예외 상황

import kotlin.math.ceil

const val COMPLETE_PERCENT = 100

class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        // (1) 남은 일수로 모두 대치시킴.
        progresses.forEachIndexed{ // 올림처리
                index, progress -> progresses[index] = ceil(((COMPLETE_PERCENT - progress) / speeds[index].toDouble())).toInt()
        }

        // 기준일 시작은 맨 처음일
        var releaseRemainDay = progresses.first()
        var releaseCount = 0
        val answer = ArrayList<Int>()
                // (2) 무조건 '일수' 기준으로 배포 시점을 나눔. (기준일 남은 일수보다 적은애들과 함께 배포)
        progresses.forEach {
        	// 기준일보다 적은애들은 지나가면서 releaseCount 증가
            if (releaseRemainDay >= it) {
                releaseCount++
            } else {
            // 기준일보다 많은 애 (끝나지 않을애)를 만나면 지금까지 증가시켜온 releaseCount 를 세고 초기화하고 기준일 재설정
                answer.add(releaseCount)
                releaseCount = 1
                releaseRemainDay = it
            }
        }
        answer.add(releaseCount)
        return answer.toIntArray()
    }
}

왜 채점표에는 이게 더 시간소요가 오래걸리는지 의문이다 ㅡㅡ

---

⭐ 풀이3

가장 최적화 되었다고 생각하는 풀이이다.
반복문의 첫, 마지막원소 처리와 OutOfBound 에 대한 처리를 모두 고려한 반복문 최적화 코드!
새로운 배포 기준 업무를 만나면 일단 배열리스트에 추가하고
그와 작거나 같은 (같이 배포될) 업무를 만날때마다 배열리스트 마지막 원소를 증가시키는 방식이다.

import kotlin.math.ceil

const val COMPLETE_PERCENT = 100

class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        val answerList = ArrayList<Int>()

        // 진도율 -> 남은 일수로 모두 대치
        progresses.forEachIndexed { index, progress ->
            progresses[index] = ceil((COMPLETE_PERCENT - progress) / speeds[index].toDouble()).toInt()
        }
        var priorRemainDay = -1

        progresses.forEach {
            if (priorRemainDay < it) {
                // 새로운 기준일 설정
                answerList.add(1)
                priorRemainDay = it
            } else {
                // 기준 일보다 적거나 같은 일수가 남은 작업들을 만나면 배포수 ++
                answerList[answerList.size - 1]++
            }
        }
        return answerList.toIntArray()
    }
}