[프로그래머스] 👨‍💻 기능 개발 / python

반응형

👨‍💻 기능 개발 문제 풀어보기

😃 나의 코드

import math

def solution(progresses, speeds):
    answer = []
    progresses = [math.ceil((100-a)/b) for a, b in zip(progresses, speeds)]
    front = 0
    for idx in range(len(progresses)):
        if progresses[front] < progresses[idx]:
            answer.append(idx-front)
            front = idx
    answer.append(len(progresses)-front)
    return answer

스택^stack/큐^queue 자료구조에 속한 문제입니다. 우선 progresses와 speeds로 나누어진 두 list를 하나의 list로 만들어봅시다. 해당 list에는 각 작업별 완료되기까지(>100%) 걸리는 시간에 대한 데이터를 저장하게 됩니다. 그에 대한 코드는 다음과 같습니다.

progresses = [math.ceil((100-a)/b) for a, b in zip(progresses, speeds)]

다음으로 해당 list를 확인하면서 결과값을 찾아야합니다. 쉽게 생각하면 전체 for loop를 돌면서 맨 앞의 데이터보다 작은 지 확인하는 for loop를 다시 써서 풀 수 있습니다. 하지만 이렇게 하면 시간 복잡도가 O(n^2)가 되어 특정 테스트 케이스에서 시간 초과를 받게 됩니다. 따라서 그 보다 낮은 시간 복잡도를 가지는 방식으로 코드를 짜야합니다.

for idx in range(len(progresses)):
    if progresses[front] < progresses[idx]:
        answer.append(idx-front)
        front = idx
answer.append(len(progresses)-front)

저는 단 한 번만 배열을 돌게하여 이 안에 끝내도록 코드를 짰습니다. 대신 front 값을 계속 업데이트 하면서 맨 앞에 있는 작업이 무엇인지 확인 할 수 있게했습니다. 이렇게 짜면 시간 복잡도가 O(n)이 되어 시간 초과를 받지 않고 문제를 해결할 수 있습니다.

Written with StackEdit.

반응형

저작자표시

'Algorithm > Problem Solving' 카테고리의 다른 글

[프로그래머스] 🔢 큰 수 만들기 / python  (0)	2019.05.08
[프로그래머스] 🖨 프린터 문제 / python  (0)	2019.02.18
[프로그래머스] 👨‍💻 기능 개발 / python  (2)	2019.02.18
[프로그래머스] 👷‍♀️ 타일 장식물 / python  (0)	2019.02.18
[프로그래머스] 👨‍🏫 정수 삼각형 / python  (0)	2019.02.18
[프로그래머스] ⚾ 숫자 야구 / python  (4)	2019.02.15