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(배열) 조건으로 예외를 처리해야 한다.