띵유로그

[프로그래머스][스택][기능개발] 본문

알고리즘

[프로그래머스][스택][기능개발]

띵유 2020. 8. 16. 21:17
반응형

내 풀이

import math
def solution(progresses, speeds):
    answer = []
    days=[]
    for i in range(len(progresses)):
        days.append(math.ceil((100-progresses[i])/speeds[i]))
    days.append(199)
    stack=[]
    stack.append(days[0])
    for i in range(len(days)-1):
        if(max(stack)>=days[i+1]):
            stack.append(days[i+1])
        else:
            answer.append(len(stack))
            stack=[]
            stack.append(days[i+1])
    return answer

소요되는 날짜를 계산해두고(days) 스택에 넣는다.
1. 처음꺼는 그냥 넣음 (days[0])
2. 그 다음부터는 이전에 넣었던 것보다 더 작으면 넣는다. (후속기능이 더 짧은 기간만 소요될때 count 하기 떄문)
3. 더 큰 숫자를 만났을 때(후속기능이 더 오래걸릴때), 이전까지 만든걸 배포하면 되므로 answer에 저장 후 스택을 비움
4. 더 큰 숫자를 만났을때 스택을 비우기때문에 마지막에는 임의의 가장 큰 숫자를 넣어줌 (days[-1]=199)

=>정리) 이전에 넣었던 것보다 더 큰 숫자를 만날 때마다 배포!


헷갈렸던점

스택의 가장 윗부분이랑만 비교하면 되는줄알았다.
생각해보니, 더 앞기능이 더 오래걸릴수도 있었다.
https://programmers.co.kr/questions/9495
예시)
progresses : [40, 93, 30, 55, 60, 65]
speeds : [60, 1, 30, 5 , 10, 7]
return : [1,2,3]

예시를 보면 앞기능부터 [1,7,3,9,4,5] 일 걸리는데, 가장 윗부분과만 비교하면 9,4,5의 경우 9에서 한번 배포하고 4,5에서 다시 배포해버린다.(9,4,5가 묶여야하므로 스택에 저장된것중 가장 큰 원소와 비교해야함)


다른사람 풀이)
1.좀 더 파이썬스러운 코드로 바꾸면 zip을 사용할 수 있음

for i in range(len(progresses)):
        days.append(math.ceil((100-progresses[i])/speeds[i]))
for p, s in zip(progresses, speeds):
	days.append(math.ceil(100-p)/s)

2. //연산자는 내림

1) 4.5//1 = 4
2) -4.5//1 = -5
이걸 이용해서 math.ceil을 사용하지 않고 올림을 할 수 있다.
(-(progresses-100) //speeds)
=> progresses-100 이 음수이기 때문

반응형

'알고리즘' 카테고리의 다른 글

[프로그래머스][힙]더맵게  (0) 2020.08.23
[프로그래머스][큐][프린터]  (0) 2020.08.23
[프로그래머스][해시][위장]  (0) 2020.08.04
[백준1874] 스택 수열  (0) 2019.08.03
[백준 11047] 동전 0  (0) 2019.07.30
Comments