기능개발

class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        var answer = intArrayOf()
        var tempProgresses = progresses.toMutableList()
        var tempStart = 0
        while(true){
            for(i in 0 .. tempProgresses.size-1){
                tempProgresses[i] += speeds[i]
            }
            if(tempProgresses[tempStart] >= 100){
                var count = 0
                for(j in tempStart .. tempProgresses.size-1){
                    if(tempProgresses[j]>= 100){
                        count += 1
                    } else {
                        tempStart = j
                        break
                    }
                }
                answer += count
            }
            if(tempProgresses.count{e-> e >= 100} == tempProgresses.size) break
        }
        
        return answer
    }
}

해당 문제는 현재 저의 실력으로 풀었으며, 최선의 방법은 아닐 수 있음을 말씀드립니다.

 

추가-----------------------------------------------------------------------------------------------------------------------------------------------------------

 

Deque를 공부하고 나서 해당문제를 Deque를 사용하여 작성해보았습니다.

import java.util.*
class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        var answer = intArrayOf()
        var pro = ArrayDeque<Int>()
        var speed = ArrayDeque<Int>()
        
        //자료입력
        for(i in 0 .. progresses.size-1){
            pro.addLast(progresses[i])
            speed.addLast(speeds[i])
        }
        var count = 0
        while(pro.size != 0){
            if(pro.peekFirst() >= 100){
                for(i in 1 .. pro.size){
                    if(pro.peekFirst() >= 100){
                        pro.removeFirst()
                        speed.removeFirst()
                        count++
                    } else {
                        break
                    }
                }
                answer += count
                count = 0
            } else{
                for(i in 1 .. pro.size){
                    pro.addLast(pro.pollFirst() + speed.peekFirst())
                    speed.addLast(speed.pollFirst())
                }
            }  
        }
        return answer
    }
}

처음 작성하였던 코드의 실행시간

테스트 1 〉	통과 (14.76ms, 65.7MB)
테스트 2 〉	통과 (14.91ms, 65.3MB)
테스트 3 〉	통과 (17.35ms, 64.7MB)
테스트 4 〉	통과 (17.58ms, 65.4MB)
테스트 5 〉	통과 (16.57ms, 65.5MB)
테스트 6 〉	통과 (19.54ms, 64.7MB)
테스트 7 〉	통과 (20.89ms, 65.1MB)
테스트 8 〉	통과 (16.06ms, 65.2MB)
테스트 9 〉	통과 (15.28ms, 66.9MB)
테스트 10 〉	통과 (20.30ms, 65.1MB)
테스트 11 〉	통과 (15.52ms, 66.4MB)

 

Deque를 사용하여 작성한 코드의 실행시간

테스트 1 〉	통과 (9.29ms, 62.2MB)
테스트 2 〉	통과 (10.61ms, 63.5MB)
테스트 3 〉	통과 (10.80ms, 63.4MB)
테스트 4 〉	통과 (9.95ms, 63.6MB)
테스트 5 〉	통과 (10.12ms, 63.3MB)
테스트 6 〉	통과 (10.55ms, 64.9MB)
테스트 7 〉	통과 (15.72ms, 63.4MB)
테스트 8 〉	통과 (11.59ms, 63MB)
테스트 9 〉	통과 (11.61ms, 62.8MB)
테스트 10 〉	통과 (11.11ms, 63.1MB)
테스트 11 〉	통과 (13.58ms, 61.8MB)

 

실행시간을 비교해보면 자료의 량이 많지 않아 확 눈에 띄지는 않지만 대부분의 실행시간이 줄어들었다는 것을 확인 할 수 있었습니다.

Deque를 공부하게 되면서 자료구조의 중요성 등을 다시금 깨닫게 되는 문제 였던것 같습니다.

 

알고리즘의 문제들 중에서 조건에 만족하면 삭제를 해야되는 경우 Deque를 사용하면 시간초과에 대한 문제에 대하여 비교적 쉽게 해결 할 수 있을거라고 생각이 듭니다.