메모
일단 스택 하나 사용하는데, 작업이 완료된 인덱스를 넣는 스택 (if prog[i] >= 100)
-> 이때, 스택에는 완료된 것 먼저 "스택"에 넣어야 꺼낼 때 같이 꺼내짐
출력 : 각 배포마다 몇 개의 기능이 배포되는지를 return
처음에 접근한 알고리즘
i = -1
while 1:
i += 1
prog[i] += speeds[i]
for j in range(len(prog)):
if prog[j] >= 100:
if j == 0: # 순차적으로 진행하니까, 맨 앞에 값이 100을 넘었다면
prog.pop(j)
ans += 1
if stack:
ans += len(stack)
stack = []
else: # 맨 앞에값이 100에 도달한게 아니라면
stack.append(prog.pop(j))
answer.append(ans)
ans = 0- <중요> 그리고 stack.pop()할 때 항상 겪었던 out of range 문제 주의해야함
- pop(i)를 수행하면, i인덱스 데이터 추출되고 그 뒤에있는 애들이 앞으로 당겨짐
- 그래서 for문에서 뻑나는거
예를들면,
나는 i++하면서 순서대로 5,4,1을 제거하고 싶어. 그래서 결과를 [3,2]만 냄기고싶어
[3,5,4,1,2] 에서 pop(1)을 했음
[3,4,1,2]가 되는데 이때, for문이나 while문할 때 i++하잖아
[3,4,1,2]에서 pop(1+1=2)을 했음
[3,4,2] 가 되어버림 ~> 내가 원했던 4가 pop되지 않고 퐁당퐁당 1이 pop되어버림!!!
그리고 이렇게 가면 out of range에러가 또 뜨겠지..!
즉! 이래서 퐁당퐁당 pop()이 됐던거임! 내가 이것을 간과했다...!
=>그래서 매번 for문이랑 pop쓸 때 주의해줘야하고,
for문이랑 쓸라면 pop한 후에 break하고 밖에서 다시 range(length) 갱신해줘야함!항상 두~세번째 테케를 먼저 적용해서 풀 생각을 하자... 테케1은 단순한 경우의 테케임...
수학문제, DP문제처럼 공식화하는? 패턴을 읽는? 문제유형들을 먼저 익혀야할까...
솔루션 코드 - 잘못 접근(?)해서 틀린
- 틀린 이유 : "순서"를 생각못함 ~> 뻘짓함
나는 스택에 넣어두고 앞에꺼가 끝나면 스택에 있는 모든 애들 꺼낸만큼 ++해줄 생각을 했음- 근데 이게 0번인덱스 데이터가 100으로 차면 스택을 다 꺼내는거라 당연 틀리게 됨...
- 바보였음ㅋ;
def solution(progresses, speeds):
answer = []
stack = []
i = -1
while progresses:
ans = 0
leng = len(progresses)
for j in range(0, leng):
progresses[j] += speeds[j]
if progresses[j] >= 100:
if j == 0: # 순차적으로 진행하니까, 맨 앞에 값이 100을 넘었다면
progresses.pop(j)
speeds.pop(j)
ans += 1
if stack:
ans += len(stack)
stack = []
answer.append(ans)
break
else: # 맨 앞에값이 100에 도달한게 아니라면
stack.append(progresses.pop(j))
speeds.pop(j)
break
if not progresses:
break
return answer
솔루션 코드 - 블로그
- 링크 : https://huidea.tistory.com/15
- 링크 : https://devmath.tistory.com/2
- 일종의 DP처럼 값을 계산을 해줬는데
- 핵심은 day 변수다. 그리고 count할 때의 방식이다.
- 맨 앞에 있는게 100이 안되면 day++해주고
- 맨 앞에 있는게 100이 넘는 순간 pop하고, cnt++
- pop했으니, 다음으로 맨 앞에 있는게 100이 넘을 때까지 day++해주는데,
- (중요) 이때, day++하기 전에 cnt에 데이터가 하나 있으니(= cnt>0) ans.append()하고 0으로 초기화
- 계속해서 day++해주다가
- 맨앞에 있는게 100이 넘는 순간 pop하고 cnt++
- pop했으니, 다음으로 맨 앞에 있는게 100이 넘을 때까지 day++해주는데,
- (중요) 이때, 핵심은 "day가 0부터가 아니고, 누적된 값이라서" 99같은게 계산하면 바로 100이 넘어가게 된다!! (즉, 예전에 이미 100을 넘었을 것이라는...! 이게 개어렵...)
- 따라서 else로 넘어가지 않고 cnt++가 되는거
def solution(progresses, speeds):
answer = []
day = 0 # 작업 일수 (배포 날짜)
count = 0 # 배포된 작업 개수
# 100 % 인지 확인하는 식 : progresses(현재 작업진도) + day(걸린 일수) * speeds(작업 속도)
while len(progresses) > 0 :
if ( progresses[0] + day * speeds[0] ) >= 100 : # 작업진도가 100% 이상이면
progresses.pop(0) # 작업진도 리스트와
speeds.pop(0) # 작업속도 리스트에서 삭제한 후
count += 1 # 배포 개수 1 증가
else :
if count > 0 : # 현재는 작업진도가 100% 이상이 아닌데, 앞에서 배포할 작업이 있었다면
answer.append(count) # 배포개수를 answer 리스트에 담아준 후
count = 0 # 초기화
day += 1 # 다음 날짜 작업을 확인하기 위해 작업 일수에 하루를 더해줌
answer.append(count) # 마지막 배포된 작업들에 대해서 append 를 실행하지 않고 while문을 빠져나왔기 때문에 처리해줘야함
return answer
Do My Best