TIL - algorithm - 스택/큐
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예제
progresses | speeds | return |
---|---|---|
[93, 30, 55] | [1, 30, 5] | [2, 1] |
[95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
풀이
-
스택/큐 자료구조는 배열의 요소가 반복적으로 제거(out)되는 것이 특징이다. 그러므로 스택/큐 를 활용하는 문제를 풀 때는 주어진 배열의 요소들을 어떤 방식(for loop, while loop)으로를 어떤 조건에서 지워나갈 것인지를 고민하는 것이 좋다.
-
위 문제에선 배포되어야 하는 순서대로 작업 진도가 적힌 배열 progresses가 주어지긴 하지만, 해당 배열을 큐(QUEUE, 선입 선출 방식)로 활용하기엔 어딘가 부족하다. 하루에 몇 개의 기능이 배포될 수 있는지를 알려면, 기능 별 진도가 100%에 도달할 때까지 며칠이 걸리는지를 알아야 하기 때문이다. 우선, 기능별 진도가 100%에 이르려면 얼마의 시간이 필요한 지를 구해보자.
def solution(progresses, speeds):
answer = []
work_days = []
for progress, speed in zip(progresses, speeds):
work_day = (100 - progress) / speed
work_days.append(int(work_day)) if work_day == int(work_day) else work_days.append(int(work_day)+1)
return answer
-
for loop
를 통해 기능 별로 완성까지 며칠이 걸리는 지를 구해work_days
배열 안에 담았다. 이제work_days
의 요소들을 일정한 조건이 충족될 때마다 반복 제거해 나가면 된다. 마침 문제에선 뒤에 있는 기능의 완성 시간이 앞선 기능의 완성 시간보다 적게 걸릴 경우 함께 배포될 수 있다는 조건이 주어졌다.while loop
를 활용하여 배열의 첫 번째 인덱스 요소의 값보다 큰 값이 나오기 전까지(함께 배포될 수 없는 기능이 나올 때까지) 순회시키도록 하자. -
만약, 배열의 첫 번째 요소보다 큰 값이 나온다면, 이전 순번의 요소들을 개수(
=i
)를answer
배열에 추가한 뒤, 기존work_days
에서 모두 out(제거)해주자. -
더불어,
IndexError
가 발생하지 않도록,i
값이 배열의 인덱스보다 커지지 않게 예외처리를 해줘야 한다.
def solution(progresses, speeds):
answer = []
work_days = []
for progress, speed in zip(progresses, speeds):
work_day = (100 - progress) / speed
work_days.append(int(work_day)) if work_day == int(work_day) else work_days.append(int(work_day)+1)
i = 0
while (work_days[0] >= work_days[i]) :
i += 1
if i >= len(work_days):
break
answer.append(i)
work_days[:i] = []
return answer
- 마지막으로,
work_days
의 요소를 반복적으로 제거할 수 있도록, 위 코드의while loop
를 또다시while loop
로 감싸도록 하자.while loop
의 반복 조건은 'work_days
안에 요소가 남아 있을 때까지'이다.
def solution(progresses, speeds):
answer = []
work_days = []
for progress, speed in zip(progresses, speeds):
work_day = (100 - progress) / speed
work_days.append(int(work_day)) if work_day == int(work_day) else work_days.append(int(work_day)+1)
while work_days:
i = 0
while (work_days[0] >= work_days[i]) :
i += 1
if i >= len(work_days):
break
answer.append(i)
work_days[:i] = []
return answer
reviews
-
while loop
중첩도for loop
중첩처럼 유용하게 활용될 수 있다! -
while loop
에서 인덱싱으로 배열을 순회할 때IndexError
발생할 수 있으므로i < len(배열)
조건으로 예외를 처리해야 한다.
Author And Source
이 문제에 관하여(TIL - algorithm - 스택/큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@fcfargo/TIL-algorithm-스택큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)