[Programmers 파이썬] 기능개발

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

 

이 문제는 파이썬의 list 자료구조에 대해 확실히 이해하고 있어야 풀 수 있던 문제같다.

처음에는 pop(0)로 그냥 풀까 하다가 반복문 내부에 O(n) 시간이 걸리는 작업을 해주면 O(n^2)의 시간이 걸리는 것을 알고 있었기에 다음과 같이 풀수 있었다.

 

def solution(progresses, speeds):
    answer = []
    total = 0

    progresses.reverse()
    speeds.reverse()

    while True:
        temp = 0
        for i in range(len(progresses)-1, -1, -1):
            progresses[i] = progresses[i]+speeds[i]


        for i in range(len(progresses)-1, -1, -1):
            if progresses[i] >= 100:
                progresses.pop()
                temp += 1
                total += 1
            else:
                break


        if temp > 0:
            answer.append(temp)
        if total == len(speeds):
            break

    return answer

 

맨 앞의 작업 진도가 다 되어있는지 확인이 중요하고 다 되어있다면 빼줘야한다.

pop(0)는 O(n) 시간이 걸리므로, list를 reverse해주고 pop()을 하여 마치 pop(0)한 효과를 보게 해주었다.

 

deque 자료구조를 사용해도 좋은 방법인것 같다!👌👌