[Python] 프로그래머스 42586. 기능개발 (Lv.2)

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

 

스택/큐를 어떻게 써야 하지? 문제2 입니다.

먼저 완료되는 작업들을 자료구조에 넣고 꺼내면서 비교하는 유형인 것도 같은데...

그냥 index를 밀어가면서 구현하는 게 더 쉬울 것 같아서 그렇게 풀이했습니다.

 

아이디어는 간단합니다. 우선순위가 현재 가장 높은 작업을 index로 가리키고, 그 작업의 남은 개발일 수만큼을 진행시켜 버립니다. (작업을 끝낸다는 얘기입니다.)

지금 index로 가리키는 작업이 끝나면 배포가 이루어지므로 현재 상황에서 배포가 가능한 작업들을 카운팅 해주고, 끝나지 않은 가장 우선순위가 높은 작업을 다음 index로 가리켜주면 됩니다.

 

/// 1차 개선

남은 시간을 매번 빼주면서 갱신하지 않고 현재 day를 갱신해주면서 개발에 필요한 일수가 day보다 작은 만큼 카운팅 해주는 식으로 구현을 바꿨습니다.

이전 코드가 `개발에 필요한 일수가 하나씩 차이나는 오름차순으로 정렬된` 최악의 경우 N번 순회(시간복잡도가 N^2)인데 개선 코드의 경우 무조건 1번 순회(시간복잡도 N)함으로서 작업을 완료합니다. 코드 라인이 줄어서 보기도 더 깔끔하네요.

 

개선 전 코드

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

    for i in range(len(progresses)):
        remain = 100 - progresses[i]
        if remain % speeds[i] == 0:
            progresses[i] = remain // speeds[i]
        else:
            progresses[i] = (remain // speeds[i]) + 1

    index = 0
    while index < len(progresses):
        develop = progresses[index]
        count = 0
        flag = True

        for i in range(index, len(progresses)):
            progresses[i] -= develop
            if progresses[i] <= 0 and flag:
                count += 1
                index = i + 1
            else:
                flag = False

        answer.append(count)

    return answer