문제점
- 문제 이해가 안됐다. 처음에 내가 문제를 이해한 방식은 작업이 병렬적으로 실행이 되고 첫 날 - 1개, 둘 째 날 2개 이런식으로 끝나게되면 첫 날에 커밋 - 1개 둘 째날에 커밋 2개 이런식으로 result가 [1,2] 이렇게 도출될 것이라고 생각하고 문제를 풀었다.
- 한 참이 지나도 문제가 이해가 안가서 다른 사람의 설명을 보고 문제를 이해했다. 그리고 그 사람의 코드를 최대한 보지 않은 채 문제를 풀려고 했다.
- 시간 복잡도는 O(n)으로 끝나는거 같은데 구현하고 보니 불필요한 로직이 많이 보였다. 이는 문제 풀이 와중에 수정을 거듭하면서 생긴 보일러 플레이트인 것으로 생각이 되는데 아무래도 설계단계에서 아직 생각이 구현으로 바로 이어지는거 같지가 않다.
풀이 방식
- 일단 모든 과제들의 끝나는 시간을 구한다.
- 모든 시간들의 과제가 끝나는 시간의 집합을 이용해서 가장 큰 값 > 다음 큰 값이 나올 Count를 구해서 result에 append한다.
- 그렇게 모인 count 들을 list로 반환하는 형식이다.
from collections import deque
def solution(progresses, speeds):
result = []
tmp_list = []
for i in range(0, len(progresses)) :
t = 0
rest = (100 - progresses[i])
if rest % speeds[i] != 0 :
t = rest // speeds[i] + 1
else :
t = rest // speeds[i]
tmp_list.append(t)
pass_index = {}
for i in range(0, len(tmp_list)):
if i in pass_index :
continue
cnt = 1
try :
while tmp_list[i] >= tmp_list[i + cnt] :
pass_index[i + cnt] = True
cnt += 1
result.append(cnt)
except :
result.append(cnt)
continue
return result
print(solution([95, 90, 99, 99, 80, 99] ,[1, 1, 1, 1, 1, 1])) # [1, 3, 2]다른 사람 풀이
이상한 함수써서 천하제일 쇼트코딩 대회 이런거 말고 가장 깔끔해보였던 풀이 방식은 아래의 코드이다.
def solution(progresses, speeds):
# [5, 10, 1, 1, 20, 1]
daysLeft = list(map(lambda x: (ceil((100 - progresses[x]) / speeds[x])), range(len(progresses))))
count = 1
retList = []
for i in range(len(daysLeft)):
try:
if daysLeft[i] < daysLeft[i + 1]:
retList.append(count)
count = 1
else:
daysLeft[i + 1] = daysLeft[i]
count += 1
except IndexError:
retList.append(count)
return retList사실 로직 자체는 내가 생각한 로직과 동일하다. 여기에서 사용된 ceil()함수는 실수를 입력햇을 때 반올림해서 정수를 반환하는 함수이다.
즉,
daysLeft = list(map(lambda n: (ceil((100 - progresses[n]) / speeds[n])), range(len(progresses))))progresses[n] / speeds[n]의 값을 반올림한 값들을 list로 만들어주는 것이다.